题目描述
思路解析
一句话答案：LeetCode 518 零钱兑换 II 求硬币无限取凑成金额的组合数。完全背包：dp[w] 记凑金额 w 的方案数，外层按硬币、内层按金额从小到大累加，如此数的是组合非排列。O(amount×k) 时间、O(amount) 空间。
零钱兑换 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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
完全背包求组合数的核心：「不选这种」+「选这种（可重复）」相加。按硬币种类分行，能天然避免重复计数。
地基：还没引入任何硬币（∅ 行）。凑出金额 0 只有「什么都不选」这 1 种方案，dp[0][0]=1。
同样在 ∅ 行：一种硬币都不用，却要凑出 1~5 元，谁也凑不出，所以这几格全是 0。哨兵行铺好。
算 dp[1][1]（前 1 种硬币、凑 1 元）：不选面额 1 → 沿用上行 dp[0][1]=0；选面额 1（可重复）→ 看本行左边 dp[1][0]=1。两条相加。
两条路相加 0+1=1，填进 dp[1][1]。引入面额 1 后，凑 1 元的组合数变成 1。
算 dp[1][2]（前 1 种硬币、凑 2 元）：不选面额 1 → 沿用上行 dp[0][2]=0；选面额 1（可重复）→ 看本行左边 dp[1][1]=1。两条相加。
两条路相加 0+1=1，填进 dp[1][2]。引入面额 1 后，凑 2 元的组合数变成 1。
算 dp[1][3]（前 1 种硬币、凑 3 元）：不选面额 1 → 沿用上行 dp[0][3]=0；选面额 1（可重复）→ 看本行左边 dp[1][2]=1。两条相加。
两条路相加 0+1=1，填进 dp[1][3]。引入面额 1 后，凑 3 元的组合数变成 1。
算 dp[1][4]（前 1 种硬币、凑 4 元）：不选面额 1 → 沿用上行 dp[0][4]=0；选面额 1（可重复）→ 看本行左边 dp[1][3]=1。两条相加。
两条路相加 0+1=1，填进 dp[1][4]。引入面额 1 后，凑 4 元的组合数变成 1。
算 dp[1][5]（前 1 种硬币、凑 5 元）：不选面额 1 → 沿用上行 dp[0][5]=0；选面额 1（可重复）→ 看本行左边 dp[1][4]=1。两条相加。
两条路相加 0+1=1，填进 dp[1][5]。引入面额 1 后，凑 5 元的组合数变成 1。
算 dp[2][1]：金额 1 比面额 2 还小，这种硬币用不上，只能照搬上一行 dp[1][1]=1。
照搬得到 1，填进 dp[2][1]。
算 dp[2][2]（前 2 种硬币、凑 2 元）：不选面额 2 → 沿用上行 dp[1][2]=1；选面额 2（可重复）→ 看本行左边 dp[2][0]=1。两条相加。
两条路相加 1+1=2，填进 dp[2][2]。引入面额 2 后，凑 2 元的组合数变成 2。
算 dp[2][3]（前 2 种硬币、凑 3 元）：不选面额 2 → 沿用上行 dp[1][3]=1；选面额 2（可重复）→ 看本行左边 dp[2][1]=1。两条相加。
两条路相加 1+1=2，填进 dp[2][3]。引入面额 2 后，凑 3 元的组合数变成 2。
算 dp[2][4]（前 2 种硬币、凑 4 元）：不选面额 2 → 沿用上行 dp[1][4]=1；选面额 2（可重复）→ 看本行左边 dp[2][2]=2。两条相加。
两条路相加 1+2=3，填进 dp[2][4]。引入面额 2 后，凑 4 元的组合数变成 3。
算 dp[2][5]（前 2 种硬币、凑 5 元）：不选面额 2 → 沿用上行 dp[1][5]=1；选面额 2（可重复）→ 看本行左边 dp[2][3]=2。两条相加。
两条路相加 1+2=3，填进 dp[2][5]。引入面额 2 后，凑 5 元的组合数变成 3。
算 dp[3][1]：金额 1 比面额 5 还小，这种硬币用不上，只能照搬上一行 dp[2][1]=1。
照搬得到 1，填进 dp[3][1]。
算 dp[3][2]：金额 2 比面额 5 还小，这种硬币用不上，只能照搬上一行 dp[2][2]=2。
照搬得到 2，填进 dp[3][2]。
算 dp[3][3]：金额 3 比面额 5 还小，这种硬币用不上，只能照搬上一行 dp[2][3]=2。
照搬得到 2，填进 dp[3][3]。
算 dp[3][4]：金额 4 比面额 5 还小，这种硬币用不上，只能照搬上一行 dp[2][4]=3。
照搬得到 3，填进 dp[3][4]。
算 dp[3][5]（前 3 种硬币、凑 5 元）：不选面额 5 → 沿用上行 dp[2][5]=3；选面额 5（可重复）→ 看本行左边 dp[3][0]=1。两条相加。
两条路相加 3+1=4，填进 dp[3][5]。引入面额 5 后，凑 5 元的组合数变成 4。
最右下角 dp[3][5]=4，就是用全部三种硬币凑出 5 元的组合总数。
边界先想清，尤其凑 0 元是 1 而不是 0。
两个高频追问——与 LC322 的区别 + 循环顺序为何能去重。
参考代码
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]复杂度
- 时间：O(amount × k)，k=面额种数，每种硬币扫一遍金额
- 空间：O(amount)，滚动成一维 dp 数组
易错点
面试追问把动画讲成自己的话
追问本题求组合数，和 LC322 求最少硬币数有何区别？
追问为什么硬币放外层就不会重复计数？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
目标和
LeetCode 494 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题