零钱兑换 II
完全背包方案数经典题：硬币可重复使用，问凑出目标金额有多少种组合。
#resource / algorithm
#type / snippet
#status / growing
#source / leetcode
#algo / dp
零钱兑换 II
题目链接：https://leetcode.cn/problems/coin-change-ii/
状态
dp[j] 表示凑出金额 j 的组合数。
转移
dp[j] += dp[j - coin]为什么这是组合不是排列
因为枚举顺序是：
- 外层枚举硬币
- 内层枚举金额
这样同一组硬币不会因为顺序不同被重复计算。
JavaScript
var change = function(amount, coins) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
for (let j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
};