别再死背背包模板:从 0-1 背包到完全背包,一次看懂零钱兑换的循环顺序

你好，我是程序员无隅

引言：很多人学背包 DP 时，最容易卡的不是公式，而是循环方向：为什么 0-1 背包一维优化要倒序，完全背包却要正序？本文结合灵茶山艾府《基础算法精讲 18》的学习笔记，用零钱兑换这道题把完全背包拆开讲：先从“选或不选”写出记忆化搜索，再 1:1 翻译成递推，最后讲清一维数组到底应该怎么更新。

一、先引入题目：零钱兑换为什么是完全背包？

1. 题目要求

以 LeetCode 322「零钱兑换」为例，题目给定一个硬币数组 coins 和一个目标金额 amount。

每种硬币可以使用任意多次，要求用最少数量的硬币凑出 amount。如果凑不出来，就返回 -1。

比如：

coins = [1, 2, 5]
amount = 11
答案 = 3

因为可以用：

5 + 5 + 1 = 11

一共 3 枚硬币。

再看一个无法凑出的例子：

coins = [2]
amount = 3
答案 = -1

因为只靠面值 2，无论选多少次，都凑不出 3。

2. 先抓住四个关键词

这题可以先压成四个关键词：

硬币可以重复选
恰好凑出 amount
求最少硬币数量
凑不出返回 -1

这里最关键的是第一句：每种硬币可以重复选。

如果每个硬币只能选一次，那就是 0-1 背包；但现在每种硬币可以反复选，所以它是完全背包。

3. 为什么要先对比 0-1 背包？

完全背包和 0-1 背包长得很像，都是在做“选或不选”。

真正的区别只有一个：

选完当前物品后，还能不能继续选它？

图里这句话很重要：

0-1 背包是“选过就走”，完全背包是“选完还能留在原地”。

这会直接决定后面的递归写法，也会决定一维 DP 到底是正序还是倒序。

二、先把背包模型讲清楚：i 到底变不变？

1. 0-1 背包：选完就不能再选

0-1 背包的意思是，每个物品最多选一次。

假设 dfs(i, c) 表示：在容量还剩 c 的情况下，从前 i 个物品里能得到的最优答案。

对于第 i 个物品，有两种选择：

1. 不选：

   dfs(i - 1, c)

2. 选：

   dfs(i - 1, c - w[i]) + v[i]

注意，选了之后是 i - 1。

因为这个物品已经用掉了，后面不能再选它。

2. 完全背包：选完还能继续选

完全背包的区别是：每种物品可以重复选。

换到零钱兑换里，硬币面值就是物品体积，每枚硬币的“价值”可以看成 1，因为我们关心的是用了几枚硬币。

对于第 i 种硬币，还是两种选择：

1. 不选：

   dfs(i - 1, c)

2. 继续选：

   dfs(i, c - coins[i]) + 1

注意，选了之后还是 i。

因为这枚硬币对应的是“一种面值”，选完一枚后，还可以继续选同一种面值。

3. 一句话区分

0-1 背包：选了当前物品，下一步看 i-1。

完全背包：选了当前物品，下一步还是看 i。

这个 i 变不变，就是 0-1 背包和完全背包最核心的区别。

三、记忆化搜索：先把 coinChange 写成递归

1. 状态怎么定义？

我们先不急着写数组，先用递归把问题表达出来。

定义：

dfs(i, c) 表示：
只考虑 coins[0..i] 这些硬币，
恰好凑出金额 c，
最少需要多少枚硬币。

这里有两个参数：

1. i：当前能使用到第几种硬币。

2. c：当前还需要凑出的金额。

最后我们要求的就是：

dfs(len(coins) - 1, amount)

2. 边界条件怎么写？

如果 i < 0，说明一种硬币都不能用了。

这时候只有一种情况是合法的：

c == 0

也就是刚好凑完了。

所以边界是：

ifi<0:
return0ifc==0elseinf

为什么凑不出来时返回 inf？

因为我们后面要求最小值。如果某条路不合法，就让它变成无穷大，这样 min 的时候自然不会选它。

3. 两种决策：不选 vs 继续选

对于第 i 种硬币，面值是 coins[i]。

如果当前金额 c 小于硬币面值，说明连一枚都放不下，只能不选：

ifc<coins[i]:
returndfs(i-1, c)

如果放得下，就有两种选择：

1. 不选当前硬币：

   dfs(i - 1, c)

2. 继续选当前硬币：

   dfs(i, c - coins[i]) + 1

取更小的硬币数量：

returnmin(dfs(i-1, c), dfs(i, c-coins[i]) +1)

这里的 dfs(i, c - coins[i]) 很关键。

它表示：已经选了一枚当前硬币，但第 i 种硬币还可以继续选，所以 i 不变。

4. 代码思路：递归 + 缓存

这段代码的思路是：

从最后一种硬币开始问；
每次判断当前硬币能不能选；
能选就比较“不选”和“继续选”；
用 @cache 避免重复计算同一个 (i,c)。

fromfunctoolsimportcache
frommathimportinf
fromtypingimportList

classSolution:
defcoinChange(self, coins: List[int], amount: int) ->int:
@cache
defdfs(i: int, c: int) ->int:
ifi<0:
return0ifc==0elseinf

ifc<coins[i]:
returndfs(i-1, c)

returnmin(dfs(i-1, c), dfs(i, c-coins[i]) +1)

ans=dfs(len(coins) -1, amount)
returnansifans<infelse-1

5. 一个很容易问的问题

有人可能会问：

为什么不写 dfs(i-1, c-coins[i])？选了一个硬币之后就不选了，不也可以吗？

其实这个逻辑已经被包含了。

我们先“选一个”，进入：

dfs(i, c - coins[i])

在这个递归里面，再选择“不选当前硬币”，就会进入：

dfs(i - 1, c - coins[i])

也就是说，递归两步就表达出了“选了一个，然后不再选”的情况。

这也是递归很强的地方：它不是只表达一步操作，而是能表达一整棵选择树。

6. 复杂度

状态只有 n * amount 个，每个状态只算一次。

所以：

时间复杂度：O(n * amount)
空间复杂度：O(n * amount)

其中 n 是 coins 的长度。

四、1:1 翻译成递推：把 dfs 变成 f 数组

1. 递归怎么翻译成数组？

记忆化搜索写清楚之后，递推其实就是把 dfs 改成数组。

递归里是：

dfs(i, c)

递推里为了处理 i < 0 的边界，通常整体往后平移一格：

dfs(i, c) -> f[i + 1][c]

含义是：

f[i + 1][c] 表示：
只考虑前 i + 1 种硬币，
恰好凑出金额 c，
最少需要多少枚硬币。

2. 初始化为什么是 f0 = 0？

f[0] 表示一种硬币都不选。

一种硬币都没有时：

1. 凑出金额 0：需要 0 枚硬币。

2. 凑出其它金额：不可能，记为 inf。

所以初始化是：

f= [[inf] * (amount+1) for_inrange(n+1)]
f[0][0] =0

3. 状态转移怎么写？

设当前硬币面值为 x。

如果 c < x，说明当前硬币放不下，只能不选：

f[i+1][c] =f[i][c]

如果 c >= x，说明可以选：

f[i+1][c] =min(f[i][c], f[i+1][c-x] +1)

这里最关键的是：

继续选时用的是 f[i+1][c-x]，不是 f[i][c-x]。

因为完全背包可以继续选当前硬币，所以它依赖的是当前行已经算出来的状态。

4. 二维递推代码

frommathimportinf
fromtypingimportList

classSolution:
defcoinChange(self, coins: List[int], amount: int) ->int:
n=len(coins)
f= [[inf] * (amount+1) for_inrange(n+1)]
f[0][0] =0

fori, xinenumerate(coins):
forcinrange(amount+1):
ifc<x:
f[i+1][c] =f[i][c]
else:
f[i+1][c] =min(f[i][c], f[i+1][c-x] +1)

ans=f[n][amount]
returnansifans<infelse-1

复杂度：

时间复杂度：O(n * amount)
空间复杂度：O(n * amount)

五、空间优化：为什么完全背包一维数组要正序？

1. 先看两个数组的滚动优化

二维递推里，计算第 i+1 行时，只会用到两类状态：

上一行：f[i][c]
当前行：f[i+1][c-x]

所以我们不一定非要保留完整二维表，只需要滚动保留两行。

也就是：

f[i % 2]
f[(i + 1) % 2]

这样空间可以从 O(n * amount) 降到 O(amount)。

不过两个数组还不是最简。既然只关心最终答案，我们还可以继续压成一个数组。

2. 一个数组时，f[c] 表示什么？

压成一维后，f[c] 表示当前已经处理过的硬币里，凑出金额 c 的最少硬币数。

初始化还是一样：

f= [0] + [inf] *amount

意思是：

凑出 0 元需要 0 枚硬币；
其它金额一开始都凑不出来。

3. 为什么 c 要从 x 开始？

二维转移里有一类情况：

c < x

这时当前硬币根本放不下，所以：

f[i+1][c] = f[i][c]

压缩成一维后，相当于：

f[c] = f[c]

这个赋值没有意义。

所以一维优化时，可以直接从 c = x 开始枚举：

forcinrange(x, amount+1):

4. 为什么完全背包是正序？

完全背包一维转移是：

f[c] =min(f[c], f[c-x] +1)

这里的关键是 f[c-x]。

对于完全背包来说，f[c-x] 应该是当前行的新值。

因为当前硬币可以重复选，我们希望 f[c-x] 已经考虑过当前硬币，然后再加一枚当前硬币。

所以必须正序：

x, x+1, x+2, ..., amount

5. 对比一下：为什么 0-1 背包是倒序？

0-1 背包里，每个物品最多选一次。

如果一维数组正序更新，就可能在同一轮里重复使用当前物品。

所以 0-1 背包要倒序：

amount, amount-1, ..., x

这样 f[c-x] 还没有被当前物品更新过，仍然是上一行的旧值。

一句话记忆：

只能选一次，就倒序；可以重复选，就正序。

但真正原因不是口诀，而是看 f[c-x] 应该来自上一行，还是当前行。

6. 一维优化代码

frommathimportinf
fromtypingimportList

classSolution:
defcoinChange(self, coins: List[int], amount: int) ->int:
f= [0] + [inf] *amount

forxincoins:
forcinrange(x, amount+1):
f[c] =min(f[c], f[c-x] +1)

ans=f[amount]
returnansifans<infelse-1

复杂度：

时间复杂度：O(n * amount)
空间复杂度：O(amount)

六、常见变形：至多、恰好、至少怎么想？

1. 背包题不只有“恰好装满”

很多背包题会在题目里换说法，比如：

1. 恰好：必须刚好组成目标值。

2. 至多：总和不能超过目标值。

3. 至少：总和要不小于目标值。

零钱兑换属于“恰好”：

硬币总金额必须等于 amount

所以凑不出来时要返回 -1，递归或递推里也需要用 inf 表示非法状态。

2. 求最值、求方案数也会影响初始化

背包问题还有一个常见变化：题目到底是在求什么？

求最大价值
求最少数量
求方案数
判断能不能做到

比如零钱兑换是求最少数量，所以非法状态适合写成 inf。

如果是“目标和”那类求方案数的问题，状态转移就不是取 min，而是用加法原理：

方案数 = 不选的方案数 + 选的方案数

所以不要只背一个模板。先看题目问的是“最值、方案数，还是可行性”，再决定初始化和转移。

3. 循环顺序怎么判断？

一维优化时，循环顺序可以这样判断：

1. 如果 f[c-x] 必须来自上一行：倒序。

2. 如果 f[c-x] 可以来自当前行：正序。

对应到背包模型：

0-1 背包：倒序
完全背包：正序

这比单纯背口诀更稳，因为你知道为什么这么写。

七、验证和常见坑

1. 用样例验证

样例一：

coins = [1, 2, 5]
amount = 11
答案 = 3

因为：

5 + 5 + 1 = 11

样例二：

coins = [2]
amount = 3
答案 = -1

因为无法凑出金额 3。

边界样例：

coins = [1]
amount = 0
答案 = 0

因为凑出 0 元不需要任何硬币。

2. 常见坑总结

1. 把完全背包写成 0-1 背包：继续选时应该是 dfs(i, c-x)，不是 dfs(i-1, c-x)。

2. 初始化忘记 inf：零钱兑换是求最小值，非法状态必须足够大，否则会污染答案。

3. 忘记 amount = 0：金额为 0 时答案是 0，不是 -1。

4. 一维优化方向写反：完全背包正序，0-1 背包倒序。

5. 以为正序只是口诀：真正原因是完全背包要用当前行的 f[c-x]，这样才能重复使用当前硬币。

八、面试话术沉淀

【问题】

零钱兑换这题为什么是完全背包？你是怎么做空间优化的？

【一句话】

零钱兑换中每种硬币可以重复使用，所以是完全背包；我先定义 dfs(i,c) 表示前 i 种硬币凑出金额 c 的最少硬币数，再把记忆化搜索 1:1 翻译成递推，最后根据当前行依赖关系把二维 DP 压缩成一维正序循环。

【关键词】

完全背包
选或不选
继续选 i 不变
inf 表示非法状态
记忆化搜索
递推
一维正序优化

【项目里怎么做】

写这类题时，我不会直接背模板，而是先看物品能不能重复选。

如果每个物品只能选一次，那选完之后状态要转到上一行，一维优化通常倒序；如果物品可以重复选，那选完之后还停留在当前行，一维优化通常正序。

在零钱兑换里，硬币可以重复使用，所以转移是 f[c] = min(f[c], f[c-x] + 1)，并且 c 从 x 正序枚举到 amount。

【面试追问】

追问一：为什么继续选时是 dfs(i,c-x)，不是 dfs(i-1,c-x)？

因为完全背包里第 i 种物品可以重复选。选了一枚当前硬币之后，还可以继续选同一种硬币，所以 i 不变。

追问二：为什么一维优化时完全背包要正序？

因为完全背包需要让 f[c-x] 使用当前行的新值，这样才能表示“当前硬币已经用过，还可以继续用”。正序遍历时，f[c-x] 已经被当前硬币更新过，符合这个语义。

追问三：0-1 背包为什么要倒序？

0-1 背包每个物品只能选一次。如果正序更新，f[c-x] 可能已经被当前物品更新过，就会导致同一个物品被重复使用。倒序可以保证 f[c-x] 还是上一行旧值。

九、最后总结

背包 DP 最重要的不是背代码，而是先判断模型：

每个物品最多选一次 -> 0-1 背包
每种物品可以重复选 -> 完全背包

0-1 背包和完全背包都在做“选或不选”，区别在于选完之后 i 怎么变：

0-1 背包：选完 i - 1
完全背包：选完 i 不变

零钱兑换是完全背包，因为每种硬币可以重复使用。

它的核心转移是：

f[c] =min(f[c], f[c-x] +1)

一维优化时正序遍历：

forxincoins:
forcinrange(x, amount+1):
f[c] =min(f[c], f[c-x] +1)

最后记住一句话：

循环方向不是死记硬背，而是看 f[c-x] 应该来自上一行，还是当前行。

这句话想明白，0-1 背包、完全背包、零钱兑换、目标和这类题就会顺很多。