【算法】动态规划第四篇背包收官——min 哨兵、计数世界与组合排列分水岭摘要DP 系列第四篇背包三课的后两讲。LC322 零钱兑换最值背包一次翻出三个缺口——min合并被赋值覆盖吃掉覆盖病第三案、哨兵-1在 min 世界传染-110冒充最优解实测算出比数学下界还小的答案 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【算法】动态规划第四篇背包收官——min 哨兵、计数世界与组合排列分水岭【算法】动态规划第四篇背包收官——min 哨兵、计数世界与组合排列分水岭摘要1. LC322 零钱兑换一次翻出三个缺口1.1 缺口一min 合并缺失——覆盖病第三案1.2 缺口二哨兵 -1 会传染本文最重要的知识点1.3 缺口三dp[c] 的巧合依赖1.4 手推表的列语义塌了1.5 结构统一外硬币2. LC518 零钱兑换 II计数世界的三条新规则2.1 弯一种子——凑 0 元是 1 种不是 0 种2.2 弯二合并符是 四族集齐2.3 弯三倒序惯性——0-1 的倒序不能带来完全背包2.4 组合 vs 排列一台机器跑出三个世界2.5 判别法不是你选模型是题目选模型2.6 手也会犯排列病121 残余2.7 最终版与逐轮互证3. 背包三课总拼图4. 毕业考三道识别题4.1 成绩单4.2 494 的两道坎4.3 奇偶守卫的数学两条路殊途同归4.4 四个 bug 与两个教训4.5 两个彩蛋4.6 进场三问终版5. 下一步区间 DP总结参考资料1. LC322 零钱兑换一次翻出三个缺口coins [1,2,5], amount 11 → 3551coins [2], amount 3 → -1。硬币无限用。完全背包 min 族最少枚数。第一版实测[1,2,5],11: 3 ✓ ← 碰巧最优解最后一枚恰好是 5多轮覆盖最后回正 [2],3: 0 ✗ ← 期望 -1。手推写的也是 -1——手推和代码又在打架 [1,3,4],6: 3 ✗ ← 正确 233 [186,419,83,408],6249: 15 ✗ ← 期望 20。算出了比数学下界还小的答案最后一行是铁证凑 6249 元最少也要 20 枚代码说 15 枚——物理上不可能的解被算出来了。三个缺口逐个看。1.1 缺口一min 合并缺失——覆盖病第三案内层硬币循环的意义是每个硬币都提供一个候选候选之间取 min。我的代码写的是赋值覆盖最后一个满足条件的硬币把前面的候选抹掉。[1,3,4],6的dp[6]候选332枚最优但4是最后遍历的硬币dp[6] 21 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 元所以amount1就是比最差还差——min 永远不会选中它除非全表都凑不出。两个连锁收益-1只允许作为最终返回值出现不允许出现在表里无解判定顺手完成dp[amount] amount→ 凑不出 → 返回-1。1.3 缺口三dp[c]的巧合依赖我的转移写的是dp[i] dp[i-c] dp[c]——凑 i 凑 (i−c) 一枚硬币 c被我拆成了两个子问题。虽然dp[c]恰好等于 1恰好有该面值的分支设的但这是隐性依赖巧合正确模板不依赖任何巧合——那枚硬币的贡献就是11数的是硬币的枚数。1.4 手推表的列语义塌了我的表是行金额、列面值宣称结果在右下。拿amount4试自己的表行 4 列 5 -1但正确答案是222。这种表结构只在最优解恰好用到最后一列硬币时碰巧成立。由此沉淀出手推的元规则行 处理进度时间每行是处理到这个进度时的完整世界快照。双序列三课里行是itext1 前缀——那时 i 就是进度背包里进度是处理完前 k 种硬币。两者同构LCS 的第 i 行 “吃进 text1 前 i 个字符后的世界”背包的第 k 行 “用过前 k 种硬币后的世界”。行永远是时间。快照式的红利行与行之间是清晰的继承 改进——两行的 diff 就是这种硬币改进了哪些格子。1.5 结构统一外硬币修复版顺手把循环结构统一到外硬币、内金额对 322 的 min 与顺序无关等价for_,c:rangecoins{// 外层硬币进度fori:c;iamount;i{// 内层金额正序完全背包dp[i]min(dp[i],dp[i-c]1)}}这样手推表行面值轮次和代码执行轨迹完全镜像——纸上推的每一格就是代码跑的每一步互证的最强形态。416外物品内容量、322、518 从此同一个骨架。2. LC518 零钱兑换 II计数世界的三条新规则amount 5, coins [1,2,5] → 45 / 221 / 2111 / 11111。求组合数。拿到题我连续换了三个模型方式数二维 → 方式数一维 → 可行性 bool 表全部发现不对劲卡壳。复盘下来是计数世界的三条规则没建立——好在前两步已经摸到了正确转移的结构dp[2][4]dp[1][4]dp[2][2]拐的是三个弯。2.1 弯一种子——凑 0 元是 1 种不是 0 种我所有表的dp[0]都填 0。计数世界的种子dp[0] 1空集是凑 0 元的唯一方式。同一个dp[0]格子三个世界三个值锚点公式退化子问题肉眼定答案题dp[0]语义416 可行性true空集凑 0可行322 最值0凑 0 元用 0 枚518 计数1凑 0 元有 1 种方式什么都不选种子错了所有方式数无根——整棵树悬空。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 排列一台机器跑出三个世界实测对照amount5, coins[1,2,5]外硬币正序: 4 ← 组合数正确答案 外硬币倒序: 1 ← 0-1 世界子集和恰为 5 的选法只有 {5} 外金额内硬币: 9 ← 排列数12 和 21 被分开数机制外金额版的转移dp[i] dp[i-c]语义是最后一枚是 c——同一个组合的不同花法顺序被分到不同分支各数一次dp[3] dp[2] ← 最后一枚是 1得 111 和 21 dp[3] dp[1] ← 最后一枚是 2得 12 合计 3 种排列但组合只有 2 种——21 和 12 被数重了外硬币版没有这个问题第 k 种硬币的所有用量在同一层一口气处理完顺序概念根本不存在。2.5 判别法不是你选模型是题目选模型4/1/9 三个数字看完问题变成拿到新题我怎么知道该进哪个世界核心原则不是你选模型是题目选模型。你只负责识别题目在哪个世界。识别只需两问。第一问方案的数量里顺序算不算数直觉测试——想象两个方案元素相同、顺序不同比如12和21问自己“题目眼里它们是同一个还是两个”题目在干什么顺序敏感吗世界凑钱12和21都是付 3 元店员眼里一样 → 不敏感组合选子集{1,2}和{2,1}是同一个子集集合无序 → 不敏感组合爬楼梯12和21经过的台阶路线不同脚的体验不同 → 敏感排列第二问物品能不能重复用只对组合世界追问数方案数计数背包 ├── 顺序敏感 → 排列外金额、内物品 └── 顺序不敏感 → 组合外物品 ├── 物品无限 → 内层正序518 └── 物品一次 → 内层倒序0-1 计数多少个子集的和为 k机制上循环结构为什么决定了数的是哪个世界外金额 按最后一步是谁分类——dp[i] dp[i-c]的每个来源是一条不同的最后一笔12和21被分进两个分支各数一次 → 排列外物品 按固定的物品顺序过账——所有方案被强制按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 手也会犯排列病121残余手推过关后列举金额 4 的三种方式我写的是1111、121、22——数量对了但121是排列式写法两枚 1 一枚 2 应写作112。手之所以写出121是因为大脑天然按掏钱顺序枚举——和外金额循环数出排列数是同一个心理根源。处方组合枚举按面值升序写天然不重不漏外硬币循环强制的正是同样的纪律。2.7 最终版与逐轮互证funcchange(amountint,coins[]int)int{dp:make([]int,amount1)dp[0]1// 空集凑 0 元的唯一方式for_,c:rangecoins{// 外层硬币进度fori:c;iamount;i{// 内层金额正序完全背包dp[i]dp[i-c]// 不用c(保持) 用一枚c}}returndp[amount]}逐轮 dp 与手推快照表完全一致边界四用例0 元→1、凑不出→0、单硬币→1、空硬币→0全绿。3. 背包三课总拼图416 分割等和子集322 零钱兑换518 零钱兑换 II世界可行性最值计数dp 值bool最少枚数方式数dp[0] 种子true01合并符||min物品可重复否0-1是完全是完全内层方向倒序正序正序循环结构外物品内容量外硬币内金额外硬币内金额无解表现dp[m][target]falsedp[amount]amount → -1dp[amount]0方法论增补接前三篇判据表问题判据出处min 世界的哨兵大而无害amount1绝不能冒充最优-110322计数世界的种子dp[0]1空集算一种方式518合并符选择可行||/ 最值 min / 计数方案堆不相交相加三课手推表布局行 处理进度时间背包的进度是硬币轮次322循环结构外物品/硬币进度内金额与手推快照镜像322方向三维外硬币正序组合 / 倒序0-1 / 外金额排列518组合枚举习惯面值升序写天然不重不漏戒掉掏钱顺序思维518覆盖病自查转移里的合并符||/min/写了吗还是写成了三案四案4. 毕业考三道识别题判别法立了两问之后用三道 LC 真题做毕业考——不提示类型纯靠题面识别世界。4.1 成绩单题真实世界判断结果377 组合总和 IV排列排列 ✓一次过名字陷阱识破题面原句顺序不同的序列被视作不同的组合才是信号组合二字是坑279 完全平方数完全背包min组合结构 ✓代码一次过物品自己生成枚举i*i而非筛选检测手推表漏了物品清单第三行9494 目标和0-1 计数排列 ✗ → 纠正转化满分实现四 bug 修复后过4.2 494 的两道坎坎一排列的视觉错觉。nums[1,1,1,1,1]的 5 个解看起来是负号位置不同的排列——被全 1 的数组骗了。顺序敏感测试打假1−11和−111元素位置一个没动不同的是负号挂在谁头上——集合差异{第2个}vs{第1个}不是顺序差异。换nums[1,2,3]立刻看清方案是选谁放负号——子集选择库存 10-1 世界。坎二符号不进 dp被代数消灭sum(P) − sum(N) target ← 题目要求 sum(P) sum(N) sum(nums) ← 恒等式 两式相加 → sum(P) (target sum) / 2“加符号使和为 target” ⇔ “选子集使和为(targetsum)/2”——标准 0-1 计数符号消失了。4.3 奇偶守卫的数学两条路殊途同归代数版sum(P) (sumtarget)/2必须是整数——世界上不存在和为 42.5 的子集方案数天然为 0锁定版表达式 sum − 2·sum(N)减去的永远是偶数 →表达式的奇偶性被 sum 锁死。[1,2], target2sum3奇所有表达式{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], target3的手推表倒序逐个过五个 1长成杨辉三角dp[4] C(5,4) 5——“选 4 个进正号集合与题面选 1 个位置放负号”C(5,1)5互补两面含 0 的自加 ×2nums[0,0,1], target1输出 4正确。原理c0时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 级是区间 DPLC516 最长回文子序列打头阵——那里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. 零钱兑换 IILeetCode 416. 分割等和子集动态规划第三篇背包第一课——贪心之死与正序倒序开关版权声明本文为博主原创文章遵循 CC 4.0 BY-SA 版权协议转载请附上原文出处链接和本声明。 【算法】动态规划第四篇：背包收官——min 哨兵、计数世界与组合排列分水岭
【算法】动态规划第四篇背包收官——min 哨兵、计数世界与组合排列分水岭摘要DP 系列第四篇背包三课的后两讲。LC322 零钱兑换最值背包一次翻出三个缺口——min合并被赋值覆盖吃掉覆盖病第三案、哨兵-1在 min 世界传染-110冒充最优解实测算出比数学下界还小的答案 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【算法】动态规划第四篇背包收官——min 哨兵、计数世界与组合排列分水岭【算法】动态规划第四篇背包收官——min 哨兵、计数世界与组合排列分水岭摘要1. LC322 零钱兑换一次翻出三个缺口1.1 缺口一min 合并缺失——覆盖病第三案1.2 缺口二哨兵 -1 会传染本文最重要的知识点1.3 缺口三dp[c] 的巧合依赖1.4 手推表的列语义塌了1.5 结构统一外硬币2. LC518 零钱兑换 II计数世界的三条新规则2.1 弯一种子——凑 0 元是 1 种不是 0 种2.2 弯二合并符是 四族集齐2.3 弯三倒序惯性——0-1 的倒序不能带来完全背包2.4 组合 vs 排列一台机器跑出三个世界2.5 判别法不是你选模型是题目选模型2.6 手也会犯排列病121 残余2.7 最终版与逐轮互证3. 背包三课总拼图4. 毕业考三道识别题4.1 成绩单4.2 494 的两道坎4.3 奇偶守卫的数学两条路殊途同归4.4 四个 bug 与两个教训4.5 两个彩蛋4.6 进场三问终版5. 下一步区间 DP总结参考资料1. LC322 零钱兑换一次翻出三个缺口coins [1,2,5], amount 11 → 3551coins [2], amount 3 → -1。硬币无限用。完全背包 min 族最少枚数。第一版实测[1,2,5],11: 3 ✓ ← 碰巧最优解最后一枚恰好是 5多轮覆盖最后回正 [2],3: 0 ✗ ← 期望 -1。手推写的也是 -1——手推和代码又在打架 [1,3,4],6: 3 ✗ ← 正确 233 [186,419,83,408],6249: 15 ✗ ← 期望 20。算出了比数学下界还小的答案最后一行是铁证凑 6249 元最少也要 20 枚代码说 15 枚——物理上不可能的解被算出来了。三个缺口逐个看。1.1 缺口一min 合并缺失——覆盖病第三案内层硬币循环的意义是每个硬币都提供一个候选候选之间取 min。我的代码写的是赋值覆盖最后一个满足条件的硬币把前面的候选抹掉。[1,3,4],6的dp[6]候选332枚最优但4是最后遍历的硬币dp[6] 21 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 元所以amount1就是比最差还差——min 永远不会选中它除非全表都凑不出。两个连锁收益-1只允许作为最终返回值出现不允许出现在表里无解判定顺手完成dp[amount] amount→ 凑不出 → 返回-1。1.3 缺口三dp[c]的巧合依赖我的转移写的是dp[i] dp[i-c] dp[c]——凑 i 凑 (i−c) 一枚硬币 c被我拆成了两个子问题。虽然dp[c]恰好等于 1恰好有该面值的分支设的但这是隐性依赖巧合正确模板不依赖任何巧合——那枚硬币的贡献就是11数的是硬币的枚数。1.4 手推表的列语义塌了我的表是行金额、列面值宣称结果在右下。拿amount4试自己的表行 4 列 5 -1但正确答案是222。这种表结构只在最优解恰好用到最后一列硬币时碰巧成立。由此沉淀出手推的元规则行 处理进度时间每行是处理到这个进度时的完整世界快照。双序列三课里行是itext1 前缀——那时 i 就是进度背包里进度是处理完前 k 种硬币。两者同构LCS 的第 i 行 “吃进 text1 前 i 个字符后的世界”背包的第 k 行 “用过前 k 种硬币后的世界”。行永远是时间。快照式的红利行与行之间是清晰的继承 改进——两行的 diff 就是这种硬币改进了哪些格子。1.5 结构统一外硬币修复版顺手把循环结构统一到外硬币、内金额对 322 的 min 与顺序无关等价for_,c:rangecoins{// 外层硬币进度fori:c;iamount;i{// 内层金额正序完全背包dp[i]min(dp[i],dp[i-c]1)}}这样手推表行面值轮次和代码执行轨迹完全镜像——纸上推的每一格就是代码跑的每一步互证的最强形态。416外物品内容量、322、518 从此同一个骨架。2. LC518 零钱兑换 II计数世界的三条新规则amount 5, coins [1,2,5] → 45 / 221 / 2111 / 11111。求组合数。拿到题我连续换了三个模型方式数二维 → 方式数一维 → 可行性 bool 表全部发现不对劲卡壳。复盘下来是计数世界的三条规则没建立——好在前两步已经摸到了正确转移的结构dp[2][4]dp[1][4]dp[2][2]拐的是三个弯。2.1 弯一种子——凑 0 元是 1 种不是 0 种我所有表的dp[0]都填 0。计数世界的种子dp[0] 1空集是凑 0 元的唯一方式。同一个dp[0]格子三个世界三个值锚点公式退化子问题肉眼定答案题dp[0]语义416 可行性true空集凑 0可行322 最值0凑 0 元用 0 枚518 计数1凑 0 元有 1 种方式什么都不选种子错了所有方式数无根——整棵树悬空。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 排列一台机器跑出三个世界实测对照amount5, coins[1,2,5]外硬币正序: 4 ← 组合数正确答案 外硬币倒序: 1 ← 0-1 世界子集和恰为 5 的选法只有 {5} 外金额内硬币: 9 ← 排列数12 和 21 被分开数机制外金额版的转移dp[i] dp[i-c]语义是最后一枚是 c——同一个组合的不同花法顺序被分到不同分支各数一次dp[3] dp[2] ← 最后一枚是 1得 111 和 21 dp[3] dp[1] ← 最后一枚是 2得 12 合计 3 种排列但组合只有 2 种——21 和 12 被数重了外硬币版没有这个问题第 k 种硬币的所有用量在同一层一口气处理完顺序概念根本不存在。2.5 判别法不是你选模型是题目选模型4/1/9 三个数字看完问题变成拿到新题我怎么知道该进哪个世界核心原则不是你选模型是题目选模型。你只负责识别题目在哪个世界。识别只需两问。第一问方案的数量里顺序算不算数直觉测试——想象两个方案元素相同、顺序不同比如12和21问自己“题目眼里它们是同一个还是两个”题目在干什么顺序敏感吗世界凑钱12和21都是付 3 元店员眼里一样 → 不敏感组合选子集{1,2}和{2,1}是同一个子集集合无序 → 不敏感组合爬楼梯12和21经过的台阶路线不同脚的体验不同 → 敏感排列第二问物品能不能重复用只对组合世界追问数方案数计数背包 ├── 顺序敏感 → 排列外金额、内物品 └── 顺序不敏感 → 组合外物品 ├── 物品无限 → 内层正序518 └── 物品一次 → 内层倒序0-1 计数多少个子集的和为 k机制上循环结构为什么决定了数的是哪个世界外金额 按最后一步是谁分类——dp[i] dp[i-c]的每个来源是一条不同的最后一笔12和21被分进两个分支各数一次 → 排列外物品 按固定的物品顺序过账——所有方案被强制按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 手也会犯排列病121残余手推过关后列举金额 4 的三种方式我写的是1111、121、22——数量对了但121是排列式写法两枚 1 一枚 2 应写作112。手之所以写出121是因为大脑天然按掏钱顺序枚举——和外金额循环数出排列数是同一个心理根源。处方组合枚举按面值升序写天然不重不漏外硬币循环强制的正是同样的纪律。2.7 最终版与逐轮互证funcchange(amountint,coins[]int)int{dp:make([]int,amount1)dp[0]1// 空集凑 0 元的唯一方式for_,c:rangecoins{// 外层硬币进度fori:c;iamount;i{// 内层金额正序完全背包dp[i]dp[i-c]// 不用c(保持) 用一枚c}}returndp[amount]}逐轮 dp 与手推快照表完全一致边界四用例0 元→1、凑不出→0、单硬币→1、空硬币→0全绿。3. 背包三课总拼图416 分割等和子集322 零钱兑换518 零钱兑换 II世界可行性最值计数dp 值bool最少枚数方式数dp[0] 种子true01合并符||min物品可重复否0-1是完全是完全内层方向倒序正序正序循环结构外物品内容量外硬币内金额外硬币内金额无解表现dp[m][target]falsedp[amount]amount → -1dp[amount]0方法论增补接前三篇判据表问题判据出处min 世界的哨兵大而无害amount1绝不能冒充最优-110322计数世界的种子dp[0]1空集算一种方式518合并符选择可行||/ 最值 min / 计数方案堆不相交相加三课手推表布局行 处理进度时间背包的进度是硬币轮次322循环结构外物品/硬币进度内金额与手推快照镜像322方向三维外硬币正序组合 / 倒序0-1 / 外金额排列518组合枚举习惯面值升序写天然不重不漏戒掉掏钱顺序思维518覆盖病自查转移里的合并符||/min/写了吗还是写成了三案四案4. 毕业考三道识别题判别法立了两问之后用三道 LC 真题做毕业考——不提示类型纯靠题面识别世界。4.1 成绩单题真实世界判断结果377 组合总和 IV排列排列 ✓一次过名字陷阱识破题面原句顺序不同的序列被视作不同的组合才是信号组合二字是坑279 完全平方数完全背包min组合结构 ✓代码一次过物品自己生成枚举i*i而非筛选检测手推表漏了物品清单第三行9494 目标和0-1 计数排列 ✗ → 纠正转化满分实现四 bug 修复后过4.2 494 的两道坎坎一排列的视觉错觉。nums[1,1,1,1,1]的 5 个解看起来是负号位置不同的排列——被全 1 的数组骗了。顺序敏感测试打假1−11和−111元素位置一个没动不同的是负号挂在谁头上——集合差异{第2个}vs{第1个}不是顺序差异。换nums[1,2,3]立刻看清方案是选谁放负号——子集选择库存 10-1 世界。坎二符号不进 dp被代数消灭sum(P) − sum(N) target ← 题目要求 sum(P) sum(N) sum(nums) ← 恒等式 两式相加 → sum(P) (target sum) / 2“加符号使和为 target” ⇔ “选子集使和为(targetsum)/2”——标准 0-1 计数符号消失了。4.3 奇偶守卫的数学两条路殊途同归代数版sum(P) (sumtarget)/2必须是整数——世界上不存在和为 42.5 的子集方案数天然为 0锁定版表达式 sum − 2·sum(N)减去的永远是偶数 →表达式的奇偶性被 sum 锁死。[1,2], target2sum3奇所有表达式{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], target3的手推表倒序逐个过五个 1长成杨辉三角dp[4] C(5,4) 5——“选 4 个进正号集合与题面选 1 个位置放负号”C(5,1)5互补两面含 0 的自加 ×2nums[0,0,1], target1输出 4正确。原理c0时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 级是区间 DPLC516 最长回文子序列打头阵——那里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. 零钱兑换 IILeetCode 416. 分割等和子集动态规划第三篇背包第一课——贪心之死与正序倒序开关版权声明本文为博主原创文章遵循 CC 4.0 BY-SA 版权协议转载请附上原文出处链接和本声明。