夜雨聆风你好，我是程序员无隅
引言：很多人学背包 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 个物品，有两种选择：
不选：
dfs(i - 1, c)选：
dfs(i - 1, c - w[i]) + v[i]
注意，选了之后是 i - 1。
因为这个物品已经用掉了，后面不能再选它。
2. 完全背包：选完还能继续选
完全背包的区别是：每种物品可以重复选。
换到零钱兑换里，硬币面值就是物品体积，每枚硬币的“价值”可以看成 1，因为我们关心的是用了几枚硬币。
对于第 i 种硬币，还是两种选择：
不选：
dfs(i - 1, c)继续选：
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，
最少需要多少枚硬币。
这里有两个参数：
i：当前能使用到第几种硬币。
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)
如果放得下，就有两种选择：
不选当前硬币：
dfs(i - 1, c)继续选当前硬币：
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] 表示一种硬币都不选。
一种硬币都没有时：
凑出金额 0：需要 0 枚硬币。
凑出其它金额：不可能，记为
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. 背包题不只有“恰好装满”
很多背包题会在题目里换说法，比如：
恰好：必须刚好组成目标值。
至多：总和不能超过目标值。
至少：总和要不小于目标值。
零钱兑换属于“恰好”：
硬币总金额必须等于 amount所以凑不出来时要返回 -1，递归或递推里也需要用 inf 表示非法状态。
2. 求最值、求方案数也会影响初始化
背包问题还有一个常见变化：题目到底是在求什么？
求最大价值
求最少数量
求方案数
判断能不能做到
比如零钱兑换是求最少数量，所以非法状态适合写成 inf。
如果是“目标和”那类求方案数的问题，状态转移就不是取 min，而是用加法原理：
方案数 = 不选的方案数 + 选的方案数所以不要只背一个模板。先看题目问的是“最值、方案数，还是可行性”，再决定初始化和转移。
3. 循环顺序怎么判断？
一维优化时，循环顺序可以这样判断：
如果 f[c-x] 必须来自上一行：倒序。
如果 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. 常见坑总结
把完全背包写成 0-1 背包：继续选时应该是
dfs(i, c-x)，不是dfs(i-1, c-x)。初始化忘记 inf：零钱兑换是求最小值，非法状态必须足够大，否则会污染答案。
忘记 amount = 0：金额为 0 时答案是 0，不是 -1。
一维优化方向写反：完全背包正序，0-1 背包倒序。
以为正序只是口诀：真正原因是完全背包要用当前行的
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 背包、完全背包、零钱兑换、目标和这类题就会顺很多。
