【算法】动态规划第四篇：背包收官——min 哨兵、计数世界与组合排列分水岭

【算法】动态规划第四篇：背包收官——min 哨兵、计数世界与组合排列分水岭

摘要

DP 系列第四篇，背包三课的后两讲。LC322 零钱兑换（最值背包）：一次翻出三个缺口——min合并被赋值覆盖吃掉（覆盖病第三案）、哨兵-1在 min 世界传染（-1+1=0冒充最优解，实测算出比数学下界还小的答案 15 < 20）、+dp[c]的巧合依赖；沉淀出哨兵配对原则的进阶版：min 世界的哨兵必须"大而无害"。LC518 零钱兑换 II（计数背包）：卡壳三弯——种子dp[0]=1（空集是凑 0 元的唯一方式）、+合并（四族合并符集齐）、正序（0-1 背包的倒序惯性不能带来完全背包）；以及整个背包家族最漂亮的一组对照实测：同一个方程跑出 4 / 1 / 9 三个数——组合、0-1、排列三个世界一次看全。至此背包三课收官：||/min/+三族合并、dp[0]的 true/0/1 三种种子、倒序/正序两组开关，全部集齐。

前置阅读：动态规划第三篇：背包第一课——贪心之死与正序倒序开关。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode

1. LC322 零钱兑换：一次翻出三个缺口

coins = [1,2,5], amount = 11 → 3（5+5+1）；coins = [2], amount = 3 → -1。硬币无限用。

完全背包 + min 族（最少枚数）。第一版实测：

[1,2,5],11: 3 ✓ ← 碰巧（最优解最后一枚恰好是 5，多轮覆盖最后回正） [2],3: 0 ✗ ← 期望 -1。手推写的也是 -1——手推和代码又在打架 [1,3,4],6: 3 ✗ ← 正确 2（3+3） [186,419,83,408],6249: 15 ✗ ← 期望 20。算出了比数学下界还小的答案！

最后一行是铁证：凑 6249 元最少也要 20 枚，代码说 15 枚——物理上不可能的解被算出来了。三个缺口逐个看。

1.1 缺口一：min 合并缺失——覆盖病第三案

内层硬币循环的意义是"每个硬币都提供一个候选"，候选之间取 min。我的代码写的是赋值覆盖：最后一个满足条件的硬币把前面的候选抹掉。[1,3,4],6的dp[6]：候选3+3=2枚最优，但4是最后遍历的硬币，dp[6] = 2+1 = 3覆盖了 2。

有意思的是手推注释里我自己写过：“dp[3]=dp[3-1]=1 dp[3-2]=1 取大还是小？不知道 => 取最小值+1 ？”——手已经摸到答案了（而且猜对了），代码没写。这是"手推和代码打架"的又一形态：不是对不上，是手推领先了代码。

这已经是覆盖病第三案：416 一维版||被覆盖吃掉"不选"分支、322 吃掉"别的硬币的候选"——同一个病，换了三次马甲。

1.2 缺口二：哨兵-1会传染（本文最重要的知识点）

我用-1初始化"不可达"的格子。-1的语义是结论（这格凑不出），但在转移里它是数字，而且是最危险的数字：

[2],3 的现场：dp[3] = dp[3-2] + dp[2] = dp[1] + 1 = (-1) + 1 = 0

-1 + 1 = 0，而 0 在 min 的世界里是"绝世好解"——哨兵冒充了最优解。6249 用例输出 15 也是同一条传染链：垃圾值 0 一路参与加法，滚出比数学下界还小的假答案。

哨兵配对原则的进阶版。198 那课的版本是"哨兵不能挡住真解"（>= 0vs> 0）；这次是：

min 世界的哨兵必须"大而无害"：不能冒充真解。

凑amount元最多用amount枚（全是 1 元），所以amount+1就是"比最差还差"——min 永远不会选中它，除非全表都凑不出。两个连锁收益：-1只允许作为最终返回值出现，不允许出现在表里；无解判定顺手完成（dp[amount] > amount→ 凑不出 → 返回-1）。

1.3 缺口三：+dp[c]的巧合依赖

我的转移写的是dp[i] = dp[i-c] + dp[c]——"凑 i = 凑 (i−c) + 一枚硬币 c"被我拆成了两个子问题。虽然dp[c]恰好等于 1（"恰好有该面值"的分支设的），但这是隐性依赖巧合：正确模板不依赖任何巧合——那枚硬币的贡献就是+1，+1数的是硬币的枚数。

1.4 手推表的"列语义塌了"

我的表是"行=金额、列=面值"，宣称"结果在右下"。拿amount=4试自己的表：行 4 列 5 =-1，但正确答案是2（2+2）。这种表结构只在"最优解恰好用到最后一列硬币"时碰巧成立。

由此沉淀出手推的元规则：

行 = 处理进度（时间），每行是"处理到这个进度时"的完整世界快照。

双序列三课里行是i（text1 前缀——那时 i 就是进度）；背包里进度是"处理完前 k 种硬币"。两者同构：LCS 的第 i 行 = “吃进 text1 前 i 个字符后的世界”，背包的第 k 行 = “用过前 k 种硬币后的世界”。行永远是时间。

快照式的红利：行与行之间是清晰的"继承 + 改进"——两行的 diff 就是"这种硬币改进了哪些格子"。

1.5 结构统一：外硬币

修复版顺手把循环结构统一到"外硬币、内金额"（对 322 的 min 与顺序无关，等价）：

for_,c:=rangecoins{// 外层：硬币（进度）fori:=c;i<=amount;i++{// 内层：金额正序（完全背包）dp[i]=min(dp[i],dp[i-c]+1)}}

这样手推表（行=面值轮次）和代码执行轨迹完全镜像——纸上推的每一格就是代码跑的每一步，互证的最强形态。416（外物品内容量）、322、518 从此同一个骨架。

2. LC518 零钱兑换 II：计数世界的三条新规则

amount = 5, coins = [1,2,5] → 4（5 / 2+2+1 / 2+1+1+1 / 1+1+1+1+1）。求组合数。

拿到题我连续换了三个模型（方式数二维 → 方式数一维 → 可行性 bool 表），全部发现不对劲，卡壳。复盘下来是计数世界的三条规则没建立——好在前两步已经摸到了正确转移的结构（dp[2][4]=dp[1][4]+dp[2][2]），拐的是三个弯。

2.1 弯一：种子——凑 0 元是 1 种，不是 0 种

我所有表的dp[0]都填 0。计数世界的种子：

dp[0] = 1：空集是凑 0 元的唯一方式。

同一个dp[0]格子，三个世界三个值（锚点公式：退化子问题肉眼定答案）：

种子错了，所有方式数无根——整棵树悬空。

2.2 弯二：合并符是+（四族集齐）

转移的正确形态：

dp[k][j] = dp[k-1][j] ← 一枚第 k 种都不用 → 继承上一行 + dp[k][j-c] ← 用一枚 → 剩 j-c 元，还在第 k 行（这种硬币还能再用！）

合并符家族至此集齐：416 可行性用||（有活路就行）、LCS 用max/ 编辑距离用min（挑最好的）、518 计数用+（两堆不相交的方案加起来）。"不用 c 的方案"和"至少用一枚 c 的方案"恰好无重叠地分割所有方案——所以相加。

我第一版还栽了继承缺失（dp[2][1]该继承dp[1][1]=1却写了 0）——"不选该硬币"的分支整个没走。覆盖病第四案：这个病从 416 跟到 322 再到 518，跟了三道题。

2.3 弯三：倒序惯性——0-1 的倒序不能带来完全背包

卡壳时我的推理是"金额 3 会用到 5 的值，5 还没算，所以需要倒排"——结论反了。一维滚动后dp[j-c]恰恰应该读到本行已更新的新值（= 已经用过一枚 c 的世界，这种硬币允许再用）——完全背包，正序。倒序读旧值 = 每种硬币最多一次 = 在解另一个题（0-1 组合计数）。

上一课"倒序保旧 / 正序取新"的口诀在这里升级成三维：

外硬币 + 正序 = 完全背包组合数 ← 518 正解 外硬币 + 倒序 = 0-1 背包组合数 外金额 + 内硬币 = 排列数

2.4 组合 vs 排列：一台机器跑出三个世界

实测对照（amount=5, coins=[1,2,5]）：

外硬币+正序: 4 ← 组合数（正确答案） 外硬币+倒序: 1 ← 0-1 世界：子集和恰为 5 的选法只有 {5} 外金额+内硬币: 9 ← 排列数：1+2 和 2+1 被分开数

机制：外金额版的转移dp[i] += dp[i-c]语义是"最后一枚是 c"——同一个组合的不同花法顺序被分到不同分支，各数一次：

dp[3] += dp[2] ← 最后一枚是 1：得 1+1+1 和 2+1 dp[3] += dp[1] ← 最后一枚是 2：得 1+2 合计 3 种（排列），但组合只有 2 种——2+1 和 1+2 被数重了

外硬币版没有这个问题：第 k 种硬币的所有用量在同一层一口气处理完，顺序概念根本不存在。

2.5 判别法：不是你选模型，是题目选模型

4/1/9 三个数字看完，问题变成：拿到新题，我怎么知道该进哪个世界？核心原则：

不是你选模型，是题目选模型。你只负责识别题目在哪个世界。

识别只需两问。

第一问：方案的数量里，顺序算不算数？直觉测试——想象两个方案，元素相同、顺序不同（比如1+2和2+1），问自己：“题目眼里，它们是同一个还是两个？”

第二问：物品能不能重复用？（只对组合世界追问）

数方案数（计数背包） ├── 顺序敏感 → 排列：外金额、内物品 └── 顺序不敏感 → 组合：外物品 ├── 物品无限 → 内层正序（518） └── 物品一次 → 内层倒序（0-1 计数："多少个子集的和为 k"）

机制上，循环结构为什么决定了数的是哪个世界：外金额 = 按"最后一步是谁"分类——dp[i] += dp[i-c]的每个来源是一条不同的"最后一笔"，1+2和2+1被分进两个分支各数一次 → 排列；外物品 = 按固定的物品顺序过账——所有方案被强制按1→2→5的固定顺序数过去，方案内部的顺序信息被抹掉 → 组合。

一个彩蛋：爬楼梯（LC70）就是排列。dp[i] = dp[i-1] + dp[i-2]翻译过来就是dp[i] += dp[i-1]（最后一阶踩 1）加dp[i] += dp[i-2]（最后一阶踩 2）——标准的外金额结构。人尽皆知的入门题和吓人的"排列数 9"，是同一个东西。

2.6 手也会犯排列病：1+2+1残余

手推过关后列举金额 4 的三种方式，我写的是1+1+1+1、1+2+1、2+2——数量对了，但1+2+1是排列式写法（两枚 1 一枚 2 应写作1+1+2）。手之所以写出1+2+1，是因为大脑天然按"掏钱顺序"枚举——和外金额循环数出排列数是同一个心理根源。处方：组合枚举按面值升序写，天然不重不漏；外硬币循环强制的正是同样的纪律。

2.7 最终版与逐轮互证

funcchange(amountint,coins[]int)int{dp:=make([]int,amount+1)dp[0]=1// 空集：凑 0 元的唯一方式for_,c:=rangecoins{// 外层硬币（进度）fori:=c;i<=amount;i++{// 内层金额正序（完全背包）dp[i]+=dp[i-c]// 不用c(保持) + 用一枚c}}returndp[amount]}

逐轮 dp 与手推快照表完全一致，边界四用例（0 元→1、凑不出→0、单硬币→1、空硬币→0）全绿。

3. 背包三课总拼图

方法论增补（接前三篇判据表）：

4. 毕业考：三道识别题

判别法立了"两问"之后，用三道 LC 真题做毕业考——不提示类型，纯靠题面识别世界。

4.1 成绩单

4.2 494 的两道坎

坎一：排列的视觉错觉。nums=[1,1,1,1,1]的 5 个解看起来是"负号位置不同的排列"——被全 1 的数组骗了。顺序敏感测试打假：+1−1+1和−1+1+1元素位置一个没动，不同的是负号挂在谁头上——集合差异（{第2个}vs{第1个}），不是顺序差异。换nums=[1,2,3]立刻看清：方案是"选谁放负号"——子集选择，库存 1，0-1 世界。

坎二：符号不进 dp，被代数消灭：

sum(P) − sum(N) = target ← 题目要求 sum(P) + sum(N) = sum(nums) ← 恒等式 两式相加 → sum(P) = (target + sum) / 2

“加符号使和为 target” ⇔ “选子集使和为(target+sum)/2”——标准 0-1 计数，符号消失了。

4.3 奇偶守卫的数学（两条路，殊途同归）

• 代数版：sum(P) = (sum+target)/2必须是整数——世界上不存在和为 42.5 的子集，方案数天然为 0
• 锁定版：表达式 =sum − 2·sum(N)，减去的永远是偶数 →表达式的奇偶性被 sum 锁死。[1,2], target=2：sum=3（奇），所有表达式{3, 1, −1, −3}全是奇数，偶数 target 永远够不着

三重守卫合读：target > sum（值域上端越界）/target < -sum（值域下端越界）/ 奇偶（数学上不存在）——都是"进 dp 之前宣判无解"。dp 只负责数数，不负责证明无解。

4.4 四个 bug 与两个教训

第一版实现：种子 0（计数世界应为 1）、正序（库存 1 必须倒序）、返回dp[target]（应为dp[n]，返回错格子第三案）、边界三缺一。

教训一（跨题迁移失灵）：种子dp[0]=1是 518 刚立的规则，隔了几道题加一次模型转化就丢了——规则被按"题"存储了，没按"世界"存储。教训二（双重错误抵消）：[1,2],2用例的假n（截断产物）被种子死光掩盖，碰巧输出 0——只修种子不修奇偶，这格立刻翻车成 1。

4.5 两个彩蛋

• 杨辉三角：[1,1,1,1,1], target=3的手推表（倒序逐个过五个 1）长成杨辉三角，dp[4] = C(5,4) = 5——“选 4 个进正号集合"与题面"选 1 个位置放负号”（C(5,1)=5）互补两面
• 含 0 的自加 ×2：nums=[0,0,1], target=1输出 4（正确）。原理：c=0时dp[i] += dp[i-0]就是dp[i] += dp[i]自加翻倍——0 选进 P 与不进是两个不同子集（和相同），每个 0 让方案数 ×2。一行代码无意识实现了进阶坑的正确答案

4.6 进场三问（终版）

① 库存：物品能用几次？（数组元素 = 1 次 → 0-1 倒序；面值 = 无限 → 完全正序） ② 顺序：元素相同顺序不同的方案，算一个还是两个？（一个 → 外物品；两个 → 外金额） ③ 值域 + 类型：target 出界 / 奇偶不合吗？dp 值是计数 / 最值 / 可行性？ （决定种子 1 / 0 / true 和合并符 + / min / ||）

第三问是毕业考补上的——dp 值类型 → 种子与合并符的映射，专治跨题迁移失灵。

5. 下一步：区间 DP

背包收官，DP 第 4 级是区间 DP（LC516 最长回文子序列打头阵）——那里dp[i][j]的两个下标不再是"两个序列的前缀"也不是"物品×容量"，而是同一个序列的区间端点；依赖方向变成"大区间依赖小区间"，计算顺序从"逐行"变成"按区间长度"。第一篇埋的伏笔（依赖方向 vs 计算顺序）在那里兑现。

总结

背包三课，三堂"世界规则"课。几个感受：

每换一个世界，种子和合并符都要重学一遍。dp[0]从 true 到 0 到 1，合并符从||到min到+——错都不在算法框架（外硬币内金额的骨架三题共用），全在世界规则（种子/合并/方向）。框架是廉价的，规则是血换的。

哨兵是 min 世界的暗礁。-1传染那次最震撼：算出比数学下界还小的答案（15 < 20），代码"自信地"输出了物理不可能的解。哨兵配对原则从 198 的"不挡真解"进化到"不冒充真解"——一条原则两次救命。

覆盖病跟了我三道题。416 吃掉"不选"、322 吃掉"别的候选"、518 吃掉"继承"——同一个病（转移里写了=而不是合并符）换了三次马甲。最后的自查口诀：写完转移先看合并符——||、min、+，你写的是哪个？还是压根写成了=？

4/1/9 是背包宇宙的全景照。同一个方程、三种循环姿势、三个数字——组合、0-1、排列。手推表（快照式）和代码轨迹镜像之后，这三个数字不再是背诵的结论，而是可以在纸上一步步走出来的必然。

下一篇：区间 DP 见。回文会在 DP 世界以新面目回归。

参考资料

• LeetCode 322. 零钱兑换
• LeetCode 518. 零钱兑换 II
• LeetCode 416. 分割等和子集
• 动态规划第三篇：背包第一课——贪心之死与正序倒序开关

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。