coins = [1, 2, 5], amount = 5

初始：dp = [1, 0, 0, 0, 0, 0]
            j=0  1  2  3  4  5

处理硬币1（外层第1轮）：
  j=1: dp[1] += dp[0] → dp[1] = 1  （{1}）
  j=2: dp[2] += dp[1] → dp[2] = 1  （{1,1}）
  j=3: dp[3] += dp[2] → dp[3] = 1  （{1,1,1}）
  j=4: dp[4] += dp[3] → dp[4] = 1  （{1,1,1,1}）
  j=5: dp[5] += dp[4] → dp[5] = 1  （{1,1,1,1,1}）
dp = [1, 1, 1, 1, 1, 1]

处理硬币2（外层第2轮）：
  j=2: dp[2] += dp[0] → dp[2] = 2  （{1,1} 和 {2}）
  j=3: dp[3] += dp[1] → dp[3] = 2  （{1,1,1} 和 {2,1}）
  j=4: dp[4] += dp[2] → dp[4] = 3  （{1,1,1,1} {2,1,1} {2,2}）
  j=5: dp[5] += dp[3] → dp[5] = 3  （{1,1,1,1,1} {2,1,1,1} {2,2,1}）
dp = [1, 1, 2, 2, 3, 3]

处理硬币5（外层第3轮）：
  j=5: dp[5] += dp[0] → dp[5] = 4  （+{5}）
dp[5] = 4 ✓

三、解法一：标准完全背包计数

public class CoinChangeII {
    
    /**
     * 518. 零钱兑换II - 完全背包计数（组合数）
     * 外层硬币，内层正序金额 → 组合数（不区分顺序）
     * 时间复杂度：O(n * amount)
     * 空间复杂度：O(amount)
     */
    public int change(int amount, int[] coins) {
        // dp[j] = 凑成金额j的方案总数（组合数）
        int[] dp = new int[amount + 1];
        dp[0] = 1;  // 金额为0，有1种方案（什么都不选）
        
        // 外层遍历硬币种类（保证每种硬币只被"考虑一次"，避免重复计数顺序）
        for (int coin : coins) {
            // 内层正序遍历金额（完全背包，允许重复使用同一硬币）
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        
        return dp[amount];
    }
}

四、解法二：为什么循环顺序影响语义（排列数vs组合数）

这是本题最值得深挖的地方，也是我认为面试最容易考到的点。

情况A：外层硬币，内层金额（当前写法）→ 组合数

每种硬币在外层遍历时只被"引入"一次。当我们在处理硬币2时，dp[3]只会从dp[1]（已经包含用硬币1的方案）累加，而不会再去考虑"先用2再用1"和"先用1再用2"的顺序。

情况B：外层金额，内层硬币 → 排列数（区分顺序）

/**
 * 如果外层遍历金额，内层遍历硬币：求排列数（区分顺序）
 * [1,2] 和 [2,1] 视为不同方案
 */
public int changePermutation(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    
    // 外层遍历金额（对每个金额，考虑所有硬币）
    for (int j = 1; j <= amount; j++) {
        // 内层遍历硬币
        for (int coin : coins) {
            if (j >= coin) {
                dp[j] += dp[j - coin];
            }
        }
    }
    
    return dp[amount];
}

用 coins=[1,2]，amount=3 验证：

组合数：{1,1,1}, {1,2} → 2种
排列数：{1,1,1}, {1,2}, {2,1} → 3种

Mermaid图：两种循环顺序的区别：

五、解法三：01背包版（每种硬币只能用一次）

如果题目变成每种硬币只能用一次，那就是01背包：内层倒序遍历。

/**
 * 变体：每种硬币只能用一次，求方案总数（01背包计数）
 * 内层倒序遍历金额 → 每种硬币最多用一次
 */
public int changeOnce(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    
    for (int coin : coins) {
        // 内层倒序！保证第i种硬币最多用一次
        for (int j = amount; j >= coin; j--) {
            dp[j] += dp[j - coin];
        }
    }
    
    return dp[amount];
}

关键对比总结：

场景	外层	内层	语义
完全背包最优化（322）	硬币	正序金额	最少硬币数
完全背包计数（518）	硬币	正序金额	组合数
完全背包排列数	金额	硬币	排列数
01背包计数	硬币	倒序金额	组合数（每个只用一次）

六、举一反三

同类题目：

LeetCode 377. 组合总和IV：求排列数，就是外层金额、内层硬币的写法
LeetCode 494. 目标和：01背包计数的变体，把符号分配问题转化成背包
LeetCode 1155. 掷骰子的N种方法：多重背包计数

计数DP通用原则：

初始值 dp[0] = 1（代表"空集"是一种合法方案）
转移用累加而非 min/max
循环顺序决定了是组合数还是排列数

七、踩坑实录

坑一：dp[0]初始化为0

dp[0]必须是1，代表"什么都不选，凑成金额0"这一种方案。如果初始化为0，所有后续累加都是0，最终答案全是0。我犯过这个错，面试时脑子短路了。

坑二：搞混组合数和排列数

518求的是组合数，但如果你把外层内层互换，求出来是排列数，数值更大。面试官如果想考你，会用小样本验证：amount=3，coins=[1,2]，正确答案是2（组合），如果你返回3那就是排列数写法了。

坑三：对"无限次"的理解

"每种硬币无限个"不等于同一金额可以用同一方案无限次。dp[j]代表凑成金额j的方案总数，每种组合只计一次，不存在重复。无限次的含义是同一面额可以在一种组合里出现多次（比如5=1+1+1+1+1，硬币1出现了5次）。

坑四：amount=0的特殊处理

题目保证amount≥0，当amount=0时，答案是1（什么都不选这一种）。但很多人没考虑这个边界，导致返回0。有了dp[0]=1的初始化，这个情况自然被覆盖了，不需要额外特判。

八、总结

零钱兑换II的核心不在于计数本身，而在于理解循环顺序对语义的影响。

最重要的两条规律：

完全背包：外层物品、内层正序金额 → 组合数（不区分顺序）
完全背包：外层金额、内层物品 → 排列数（区分顺序）

把这两者和322（最优化）放在一起理解，背包问题的计数和最优化就彻底打通了。