编写代码,计算出把100元换成1元,5元,10元的零钱,有多少种方式。
时间: 2024-09-30 18:04:15 浏览: 40
这个问题可以使用动态规划的方法来解决。假设 dp[i][j] 表示有 i 元的情况下,能组成 j 张面额最大的纸币的方式数。对于100元的情况,我们可以从最大面额10元开始,逐次考虑5元和1元,更新dp数组。
以下是 Python 的代码实现:
```python
def count_change(coins, amount):
dp = [[0 for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
# 初始化,没有钱的情况下,只有0种组合
for i in range(amount + 1):
dp[0][i] = 1
# 对于每一种硬币,从最大到最小
for coin_index in range(1, len(coins) + 1):
coin_value = coins[coin_index - 1]
for remaining_amount in range(coin_value, amount + 1):
dp[coin_index][remaining_amount] += dp[coin_index - 1][remaining_amount]
# 如果剩余金额大于当前硬币值,还可以用这个硬币
if remaining_amount >= coin_value:
dp[coin_index][remaining_amount] += dp[coin_index][remaining_amount - coin_value]
return dp[-1][-1]
coins = [1, 5, 10]
amount = 100
ways = count_change(coins, amount)
print(f"将{amount}元换成{coins}的零钱,有{ways}种方式.")
阅读全文