二维数组解决零钱兑换II
时间: 2023-10-03 11:05:37 浏览: 89
对于零钱兑换问题 II,可以使用动态规划来解决。假设有一个数组 coins 存储了不同面额的硬币,我们需要计算凑成总金额 amount 的不同组合数。
首先,我们定义一个二维数组 dp,其中 dp[i][j] 表示在使用前 i 个硬币的情况下,凑成金额 j 的组合数。
初始化 dp 数组:对于任意的 i,dp[i][0] 都设为 1,表示凑成金额为 0 的组合数为 1。
然后,我们可以根据以下递推关系计算 dp 数组:
对于第 i 个硬币,我们有两种选择:
- 不使用第 i 个硬币,那么 dp[i][j] = dp[i-1][j];
- 使用第 i 个硬币,那么 dp[i][j] = dp[i][j-coins[i-1]]。
最终的答案即为 dp[len(coins)][amount],其中 len(coins) 表示硬币的个数。
以下是使用 Python 实现的代码示例:
```
def change(amount, coins):
dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
for i in range(len(coins) + 1):
dp[i][0] = 1
for i in range(1, len(coins) + 1):
for j in range(1, amount + 1):
if j >= coins[i-1]:
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[len(coins)][amount]
```
这样,change(amount, coins) 函数会返回凑成总金额 amount 的不同组合数。希望能对你有所帮助!如果有其他问题,请随时提问。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)