LeetCode 518. 零钱兑换 II
题目描述
思路分析
完全背包组合问题
这个问题可以使用动态规划来解决，类似于背包问题。
我们可以创建一个一维数组
dp，其中dp[i]表示凑成金额i的硬币组合数。对于每个硬币面额
coin，我们遍历数组dp，更新每个金额的组合数。具体来说，对于每个金额
i，我们计算dp[i-coin]（即在凑成金额i-coin的基础上，再加上一个面额为coin的硬币）的组合数，将其累加到dp[i]上。最终，
dp[amount]即为所求的答案。
参考代码
1
2
3
4
5
6
7
8
9
10
11
func change(amount int, coins []int) int {
// dp[i] 表示凑成金额 i 的硬币组合数
dp := make([]int, amount+1)
dp[0] = 1
for _, coin := range coins {
for i := coin; i <= amount; i++ {
dp[i] += dp[i-coin]
}
}
return dp[amount]
}
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！