零钱兑换 II 图解题解

这道题到底在问什么

coins

[1, 2, 5]

amount

5

输出

4

先想最直接的笨办法

最直接的想法：递归枚举「面额 1 用几枚、面额 2 用几枚、面额 5 用几枚」，凑够 5 就记一种。可这样不同硬币的搭配会指数爆炸，而且「凑剩下 3 块有几种」这种子问题会被反复重算，慢得离谱。（动画第 3 步）

最优解：一步一步想明白

1. 3最直接的想法：递归枚举「面额 1 用几枚、面额 2 用几枚、面额 5 用几枚」，凑够 5 就记一种。可这样不同硬币的搭配会指数爆炸，而且「凑剩下 3 块有几种」这种子问题会被反复重算，慢得离谱。
2. 4转折：把「凑 j 有几种」记进 dp[j]，重叠子问题就只算一次。状态：dp[j]=凑出 j 的组合数；转移：加入面额 coin 后 dp[j] += dp[j−coin]（凑 j 的新法 = 先凑好 j−coin 再添一枚 coin）。外层枚举硬币、内层金额从小到大，就保证同一种组合只按「硬币种类顺序」数一次，不会把 2+1 和 1+2 当两种。
3. 5dp = [1,0,0,0,0,0]表头是金额 0 到 5，一行 6 格，全程不变。dp[0]=1：凑 0 块有一种办法，就是什么都不拿（空组合）。其余先记 0，还没开始放硬币。
4. 6coin=1先放面额 1。从 j=1 到 5 依次 dp[j] += dp[j−1]：dp[1]=dp[0]=1、dp[2]=dp[1]=1…一路全是 1。意思是只用 1时每个金额都只有「全用 1」这一种凑法。
5. 7dp[2] += dp[0]换面额 2，内层金额仍从小到大。先填 dp[2]：在原来「1+1」之外，多了一种「直接一枚 2」，来源是 dp[2−2]=dp[0]=1。所以 dp[2] = 1 + 1 = 2。
6. 8dp[3] += dp[1]dp[3]：加一枚 2 后剩 1，dp[1]=1（即 2+1）。dp[3] = 原来的 1（1+1+1）+ 1 = 2。
7. 9dp[4] += dp[2]dp[4] 用到刚更新过的 dp[2]=2——这正是从小到大的妙处：面额 2 可以重复用。dp[4] = 1 + 2 = 3（对应 1+1+1+1、2+1+1、2+2）。
8. 10dp[5] += dp[3]面额 2 收尾，dp[5] += dp[3]=2，从 1 涨到 3。现在只用 1 和 2，凑 5 已经有 3 种。还差面额 5 没放。
9. 11coin=5，j 从 5 起换面额 5。内层金额从 coin=5 起步，所以金额 小于 5 的格子这一轮碰都不碰（不可能用上一枚 5），dp[1] 到 dp[4] 保持不变。只剩 dp[5] 要更新。
10. 12dp[5] += dp[0]dp[5] += dp[5−5]=dp[0]=1：多出来的这一种就是单独一枚 5。dp[5] 从 3 变成 4。三种硬币全放完了。
11. 13dp[5] = 4表格最后一格 dp[5] = 4 就是答案，对应那 4 种组合：5、2+2+1、2+1+1+1、1×5。返回 4。
12. 16完全背包内层从小到大（硬币可重复），0-1 背包内层从大到小（每个只用一次）。求组合数外层套物品、内层套容量；求排列数把两层对调。这一句记牢，一类题全通。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def change(self, amount, coins):
        dp = [0] * (amount + 1)
        dp[0] = 1                       # 凑 0 元：空集算一种
        for coin in coins:             # 外层硬币 → 只数组合
            for x in range(coin, amount + 1):   # 正序 → 每币可重复用
                dp[x] += dp[x - coin]
        return dp[amount]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;                          // 凑 0 元：空集算一种
        for (int coin : coins)              // 外层硬币 → 只数组合
            for (int x = coin; x <= amount; x++)   // 正序 → 完全背包
                dp[x] += dp[x - coin];
        return dp[amount];
    }
};

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;                          // 凑 0 元：空集算一种
        for (int coin : coins)              // 外层硬币 → 只数组合
            for (int x = coin; x <= amount; x++)   // 正序 → 完全背包
                dp[x] += dp[x - coin];
        return dp[amount];
    }
}

# 每个物品可无限次使用，求凑出 W 的组合数
dp = [0] * (W + 1)
dp[0] = 1                            # 计数初值 1（最值题改 0 或 INF）
for x in items:                      # 求组合数：外层物品
    for j in range(x, W + 1):        # 完全背包：内层从小到大
        dp[j] += dp[j - x]           # 计数用 +=；最值用 min/max
return dp[W]

复杂度

面试官可能追问