python用100元换10元,5元,1元共50张,每种至少一张,一共几种兑换方式
时间: 2023-07-09 11:11:38 浏览: 109
这是一个经典的硬币找零问题,可以使用动态规划算法求解。假设需要找零 x 元,设 dp[i][j] 表示前 i 种硬币,凑成 j 元的方案数。其中 i 取值范围为 1 到 3,分别表示 10 元、5 元和 1 元三种硬币。j 取值范围为 1 到 x,表示需要凑成的金额数。
初始化:当 j 为硬币面值时,方案数为 1,否则为 0。
状态转移方程:对于第 i 种硬币,考虑选或不选该硬币。如果不选,则方案数为 dp[i-1][j];如果选,则方案数为 dp[i][j-coins[i]],其中 coins[i] 表示第 i 种硬币的面值。因此,dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]。
最终答案为 dp[3][x],即三种硬币凑成 x 元的方案数。
以下是 Python 代码实现:
```python
def coin_change(x):
coins = [0, 10, 5, 1] # 硬币面值
n, m = 3, x # n 表示硬币种类数,m 表示需要凑成的金额数
dp = [[0] * (m+1) for _ in range(n+1)] # 初始化 dp 数组
for i in range(1, n+1):
dp[i][coins[i]] = 1 # 初始化第 i 种硬币的方案数
for i in range(1, n+1):
for j in range(1, m+1):
if j >= coins[i]:
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]
else:
dp[i][j] = dp[i-1][j]
return dp[3][x]
print(coin_change(100)) # 输出方案数
```
根据题目要求,每种硬币至少一张,因此需要在上述算法的基础上将方案数减去其中至少一种硬币为零的情况。具体做法是将 dp[1][j]、dp[2][j]、dp[3][j] 分别减去 dp[0][j],即在不限制硬币数量的情况下,凑成 j 元的方案数。最终答案为 dp[3][x] - dp[0][x]。