零钱兑换 II (Coin Change 2)

动态规划（Dynamic Programming）往往是算法面试中的一道坎。它的核心思想其实并不复杂，但难点在于如何把一个大问题拆解成状态转移公式。

今天我们要讨论的是一道经典的完全背包变体问题：零钱兑换 II (Coin Change 2)。

0x01 问题描述

给你一组不同面值的硬币（coins），以及一个目标金额（amount）。假设每种硬币的数量是无限的，请问：凑出该目标金额，一共有多少种不同的组合方式？

注意，这里求的是组合 (Combinations)，顺序是不重要的。比如 1 + 2 和 2 + 1 在这里被视为同一种方案，因为它们最终构成的「钱包」里都是一枚1元和一枚2元。

0x02 举个例子

假设我们手头有三种硬币，面值分别是 [1, 2, 5]，目标是凑出 5 元。

稍微列举一下，我们会发现一共有 4 种凑法：

1
2
3
4

1. **5**  (直接拿一张5元)
2. **2 + 2 + 1**
3. **2 + 1 + 1 + 1**
4. **1 + 1 + 1 + 1 + 1**

所以，答案是 4。

0x03 核心思维：填表法

如果不使用递归回溯，而是使用动态规划，本质上就是一张表格的填空游戏。

我们定义一个一维数组 dp，其中 dp[i] 的含义是：凑出金额 i，一共有多少种方案。

一开始，除了 dp[0] = 1（凑出0元只有一种方法：什么都不拿），其他格子都初始化为 0。然后，我们一枚硬币、一枚硬币地去更新这张表格。

状态转移的逻辑

假设我们现在开始处理面值为 2 的硬币。当我们要凑出金额 5 时，摆在我们面前的只有两种选择：

1. 不使用这枚2元硬币。 那么方案数就等于「在没有2元硬币参与的情况下，凑出5元的方案数」。这个数值其实就是表格里旧的 dp[5]。

2. 使用这枚2元硬币。 既然确定用了一枚2元，那么剩下的任务就是凑出 3 元（5 - 2 = 3）。这有多少种方法呢？直接查看表格里的 dp[3] 就可以了。

把这两种情况加起来，就是新的 dp[5] 的值。

这就得到了我们的状态转移方程：

1

dp[i] = dp[i] (旧方案：不选当前硬币) + dp[i - coin] (新方案：选当前硬币)

0x04 步骤演示

让我们模拟一下整个过程。

1. 初始状态：dp[0] = 1，其余为 0。
2. 第一轮：处理硬币 1。 遍历整个表格，你会发现凑出任何金额都只有 1 种方法（全用1元）。表格被填满为全 1。
3. 第二轮：处理硬币 2。 在刚才的基础上，看看能不能通过「加入2元」产生新方案。比如凑 2 元，原本有 1+1，现在多了 2，方案数变为 2。
4. 第三轮：处理硬币 5。 继续叠加。

这里有一个关键点：我们必须先遍历硬币，再遍历金额。也就是说，先处理完 1 的所有情况，再处理 2。这样就保证了我们永远是「在 1 的基础上加 2」，而不会出现「在 2 的基础上加 1」这种回头路，从而完美避开了排列重复的问题。

交互式演示

Created by Gemini

通过下面的动画，直观地看到这个填表过程。注意观察当切换下一枚硬币时，表格是如何在旧值的基础上进行叠加更新的。

0x05 代码实现

转化为代码非常简洁。我们使用了 Go 语言作为示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func change(amount int, coins []int) int {
    // 1. 初始化 DP 数组
    dp := make([]int, amount+1)
    dp[0] = 1

    // 2. 外层循环：遍历硬币
    for _, coin := range coins {
        // 3. 内层循环：遍历金额
        // 注意：j 从 coin 开始，因为比 coin 小的金额无法使用这枚硬币
        for j := coin; j <= amount; j++ {
            dp[j] += dp[j-coin]
        }
    }
    return dp[amount]
}

0x06 复杂度分析

• 时间复杂度：$O(\text{amount} \times N)$。我们需要对每一枚硬币，都完整地遍历一次 DP 数组。
• 空间复杂度：$O(\text{amount})$。得益于滚动数组的思想，我们只需要一个一维数组就能将其拿下。

进阶：循环顺序的奥秘

在完全背包问题中，循环的嵌套顺序是一个非常经典的面试考察点：如果我们交换内外层循环（先遍历金额，再遍历硬币），结果会变成什么？

结果是：我们会算出排列数，而不是组合数。

• 先遍历硬币 (Coins First)：这就像我们在兜里抓钱，先把 1 元的都拿完，再去拿 2 元的。硬币 1 永远在硬币 2 之前被考虑，所以结果是无序的集合，即组合。
• 先遍历金额 (Amount First)：这就像爬楼梯，每次迈步都可以选 1 阶或 2 阶。在凑 3 元时，先拿 1 再拿 2，和先拿 2 再拿 1，会被视为两个不同的动作序列，即排列。

下图清晰地展示了这两种路径的区别：

  graph TB
    %% =====================
    %% 组合数（Combinations）
    %% =====================
    subgraph Comb["🎯 组合数 Combinations<br/><br/>特点：先遍历硬币，避免重复计数"]
        direction TB
        C1["💰 硬币 1<br/>coin[0]"]
        C2["💰 硬币 2<br/>coin[1]"]
        C3["💰 硬币 3<br/>coin[2]"]
        
        C1 ==>|"处理完所有金额"| C2
        C2 ==>|"只在硬币1的基础上累加"| C3
        
        R1["✅ 结果示例<br/>{1,2} ≡ {2,1}<br/>只计数一次"]
        
        C3 -.-> R1
        
        Note1["⚠️ 后面的硬币<br/>不会回头使用前面的"]
        C2 -.->|"单向处理"| Note1
    end

    %% =====================
    %% 排列数（Permutations）
    %% =====================
    subgraph Perm["🔄 排列数 Permutations<br/><br/>特点：先遍历金额，允许不同顺序"]
        direction TB
        A1["💵 当前金额 i<br/>amount = i"]
        
        P1["💰 硬币 1"]
        P2["💰 硬币 2"]
        P3["💰 硬币 3"]
        
        A1 ==>|"尝试所有硬币"| P1
        A1 ==>|"尝试所有硬币"| P2
        A1 ==>|"尝试所有硬币"| P3
        
        R2["✅ 结果示例<br/>{1,2} ≠ {2,1}<br/>分别计数"]
        
        Next["➡️ 递归到下一个金额<br/>amount = i - coin[j]"]
        
        P1 -.-> Next
        P2 -.-> Next
        P3 -.-> Next
        Next -.-> R2
    end

    %% =====================
    %% 样式定义
    %% =====================
    classDef coinStyle fill:#4A90E2,stroke:#2E5C8A,stroke-width:2px,color:#fff
    classDef amountStyle fill:#50C878,stroke:#2E7D4E,stroke-width:2px,color:#fff
    classDef resultStyle fill:#FFB84D,stroke:#CC8A3D,stroke-width:3px,color:#000
    classDef noteStyle fill:#E8E8E8,stroke:#999,stroke-width:2px,color:#333,stroke-dasharray: 5 5
    
    class C1,C2,C3,P1,P2,P3 coinStyle
    class A1 amountStyle
    class R1,R2 resultStyle
    class Note1,Next noteStyle

对于本题（求组合数），请务必记住：先遍历硬币，再遍历金额。