零钱兑换 II 为什么是完全背包计数？遍历顺序如何避免重复组合？

简化版

零钱兑换 II 求的是组合数，不关心硬币顺序。用 dp[j] 表示凑出金额 j 的组合数，外层遍历硬币，内层金额正序遍历，这样每种硬币可以重复使用，同时不会把 [1,2] 和 [2,1] 算成两种。

详细版

初始化 dp[0]=1，表示凑出金额 0 有一种“什么都不选”的方式。对每个硬币 coin，遍历 j=coin..amount，执行 dp[j] += dp[j-coin]。正序遍历让当前硬币可以重复使用，外层固定硬币顺序则保证组合不会按排列重复计数。

如果外层金额、内层硬币，会统计排列数，因为同一组硬币的不同顺序会被重复计算。时间复杂度 O(amount * coins.length)，空间复杂度 O(amount)。

完整版教学

一、先分清组合数和排列数

给定 amount = 5，coins = [1,2,5]，合法组合有：

5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

1+2+2 和 2+1+2 不是不同答案，因为题目只看硬币数量组合，不看顺序。

二、为什么是完全背包

每种硬币可以使用无限次，所以是完全背包；目标不是最大价值，也不是最少硬币数，而是方案数量。

维度	本题含义
物品	每种硬币面额
容量	目标金额
使用次数	无限次
目标	组合方案数

记忆钩子：最少硬币是最优化 DP，零钱兑换 II 是计数 DP。

三、状态和初始化

定义：

dp[j]：使用已经遍历过的硬币，凑出金额 j 的组合数

dp[0]=1 是计数 DP 的起点。它表示凑出 0 元有一种空组合；当某个硬币刚好等于金额时，dp[coin] += dp[0] 才能产生 1 种组合。

四、为什么外层必须遍历硬币

外层遍历硬币意味着组合中的硬币顺序被固定为词典顺序。例如先处理 1，再处理 2，组合只会以“若干个 1 后加入若干个 2”的方式被统计一次。

外层 coin：
先只用 1 的组合
再在这些组合基础上加入 2
最后加入 5

如果外层金额、内层硬币，凑金额 3 时会从金额 1 加硬币 2，也会从金额 2 加硬币 1，于是 [1,2] 和 [2,1] 都被算进去。

五、为什么金额要正序

完全背包允许同一种硬币重复使用。处理 coin=2 时，如果正序遍历金额：

dp[2] 可以由 dp[0] 得到
dp[4] 可以由本轮刚更新的 dp[2] 得到

这正好表示可以用两个 2。如果倒序，就会禁止当前硬币重复使用，变成 0-1 背包。

六、代码模板

int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}

这段代码的两个循环顺序都不能随便交换：外层硬币保证组合计数，内层正序保证完全背包。

七、常见误区与追问

误区：把零钱兑换 I 的最少硬币转移照搬过来。 本题求方案数，用加法累加，不取最小值。
误区：外层金额内层硬币。 这会统计排列数，导致顺序不同的同一组合重复。
误区：金额倒序遍历。 倒序会让每种硬币最多使用一次，不符合无限硬币。
追问：为什么 dp[0]=1？ 空组合是构造其他组合的基础。
追问：和 0-1 背包计数有什么区别？ 0-1 背包内层倒序，完全背包内层正序。
追问：复杂度是多少？ 时间 O(amount * m)，空间 O(amount)，其中 m 是硬币种类数。

八、加强记忆

零钱兑换 II 最重要的是同时记住两个词：“完全”和“组合”。完全意味着同一硬币能重复用，所以金额正序；组合意味着顺序不重要，所以外层固定硬币，避免 [1,2] 和 [2,1] 重复计数。dp[0]=1 是所有计数组合的起点，转移用 += 表示把当前硬币加入已有金额的组合。只要能解释循环顺序，这题就不只是会背模板。

简化版

详细版