零钱兑换 II 图解题解

零钱兑换 II 到底在数什么

面额固定、每种能无限取用的硬币 coins=[1,2,5]，问凑出金额 amount=5 有多少种组合。组合只看各面额用几枚、不计先后。凑 5 元有四种：5 个 1、3 个 1 加 1 个 2、1 个 1 加 2 个 2、1 个 5，答案 4。

为什么不能把所有凑法枚举一遍

把每种硬币各用几枚的所有搭配摆出来逐个验证，面额一多、金额一大，数量成倍翻，试不完。而且不少搭配前半截重叠、被反复重算——凑到 3 元再往上加，和从头拼是同一批中间结果，记下来复用就是动态规划。

dp 数组怎么定义，dp[0] 为什么必须是 1

dp[w] 表示凑出金额 w 的组合数，答案是 dp[amount]。起点 dp[0]=1：凑出金额 0 只有「什么都不拿」这一种。这个 1 是所有累加的种子，写成 0 的话每次 dp[w]+=dp[w-c] 都在加 0，整张表全归零。

这里套的是完全背包（背包 = 把物品装进定容的包；硬币是物品、金额是容量，每种可取无限枚）。

为什么硬币在外层、金额在内层数的才是组合数

转移 dp[w]+=dp[w-c]：凑金额 w，就在已凑出 w-c 的方案上添一枚面额 c。数出组合还是排列，全看两层循环谁在外。外层按硬币枚举，轮到 c 时 dp[w-c] 里累加过的只有「排在 c 之前引入的面额」，所以任何一种组合都只在它用到的最大面额那轮生成一次，天然不重复；5=1+2+2 只在面额 2 那轮按 1 后接 2 生成，不会冒出 2 在前的版本。

把循环换个个儿、金额在外硬币在内，就成了对每个金额都重挑所有面额，1+2 与 2+1 各数一次，得到的是排列数，那是 LeetCode 377 组合总和 Ⅳ。

内层金额还必须从小到大：dp[w] 要用本轮（已加过 c）的 dp[w-c] 新值，这是同种硬币反复取用的通道；从大到小则 dp[w-c] 停在没加 c 的旧值，每种只能用一次，成了 01 背包（每样只取一次）。

拿 coins=[1,2,5]、amount=5 手工填一遍

dp 初值 [1,0,0,0,0,0]，下标 0 到 5。处理面额 1，w 从 1 到 5，dp[w]+=dp[w-1]：dp[1]=1、dp[2]=1，后面顺次也变 1，整行 [1,1,1,1,1,1]。

处理面额 2，w 从 2 到 5，dp[w]+=dp[w-2]：dp[2]=1+dp[0]=2，dp[3]=1+dp[1]=2，dp[4]=1+dp[2]=3，dp[5]=1+dp[3]=3，整行 [1,1,2,2,3,3]。处理面额 5，只到 w=5：dp[5]=3+dp[0]=4，就是答案。

复杂度多少，哪三处最容易写错

时间 O(amount×k)，k 是面额种数：外层每种硬币一轮、内层从面额扫到 amount。空间 O(amount)：dp 压成一维就地覆盖旧值，这种把二维表滚成一行的写法叫滚动数组。

三处最常踩坑：循环写反、金额在外硬币在内，答案变成排列数，样例会比 4 大；内层从大到小，同种硬币只能用一次，退化成 01 背包，方案少一批；dp[0] 忘置 1，累加没种子，dp[amount] 会是 0。

Python

def change(amount, coins):
    dp = [1] + [0] * amount   # dp[0]=1
    for c in coins:           # 外层枚举硬币
        for w in range(c, amount + 1):
            dp[w] += dp[w - c]
    return dp[amount]

C++

int change(int amount, vector<int>& coins){
    vector<long> dp(amount + 1, 0);
    dp[0] = 1;
    for(int c : coins)
        for(int w = c; w <= amount; ++w)
            dp[w] += dp[w - c];
    return (int)dp[amount];
}

Java

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