[!info] related notes 动态规划 背包 DP 零钱兑换

零钱兑换 II

题目链接：https://leetcode.cn/problems/coin-change-ii/

状态

处理完当前硬币种类后，dp[j] 表示只使用这些种类凑出金额 j 的组合数。面值按题意是互不相同的正整数，每种可重复使用。

转移

dp[j] += dp[j - coin]

为什么这是组合不是排列

因为枚举顺序是：

• 外层枚举硬币
• 内层枚举金额

这样同一组硬币不会因为顺序不同被重复计算。dp[0] = 1 表示空组合，是后续转移的起点；若输入重复面值而不去重，会把同一面值当成不同种类重复计数。金额放外层、硬币放内层通常会计数排列，不能直接交换循环。

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];
};