《程序设计思维与实践》到了第九周作业题给我的第一感觉是暴力不是不能写但大概率超时。这周的题单核心是动态规划包含背包、子序列划分、区间合并三类典型问题正好把教材上零散的知识点串成了一条线。我花了三个晚上完成并反复调试过程中踩过初始化、循环顺序、边界条件几个坑也收获了几个能直接迁移到其他题的思考习惯。这篇就记录我自己的拆题、推状态、写转移、调试的完整过程给正在做同周作业或正在练 dp 的人一个参考。先说一个总印象第九周的作业题并不是“难到看不懂”而是“每一个坑都藏在细节里”。如果你只看最终代码会觉得状态转移很简单可一旦自己动手就会发现“为什么这里要取 min”“为什么循环要反着写”“为什么初始化不能全填 0”。这些问题的答案恰恰是动态规划真正要训练的东西。1. 拿到第九周作业题时我先做了三件事1.1 先压缩题干提炼出“问题模型”我拿到题目后的第一件事不是写代码而是把题干压缩成两三行。比如本周第一道题原题描述很长又是价值又是体积又是“尽量装满”但压缩之后其实是有若干物品每件有体积和价值背包容量固定求容量限制下的最大总价值。这就是最经典的 0-1 背包模型。这一步为什么重要因为动态规划的题目百分之八十的难度在于识别模型。一旦你看出它是背包、是 LIS、是区间合并后续的状态定义和转移方程其实是有固定套路的。如果你连模型都没看出来自然不知道 dp 数组开几维、下标代表什么。我自己的习惯是用“名词短语”压缩题干比如“选或不选每件只能用一次” → 0-1 背包“要求相对顺序不变从序列里挑出最长的递增子序列” → LIS“相邻两堆可以合并合并有代价求最小总代价” → 区间 DP。做完这一步题目就从几百字压缩成了几个关键词脑子一下就清楚了。1.2 用暴力拿样例再想优化方向压缩题干之后我会先在心里跑一遍暴力做法甚至在小数据下真写一版暴力。比如子序列划分那道题暴力就是枚举所有划分方案数据小的时候能跑但数据一大一定超时。这时候我再问自己暴力过程里有没有重复计算的部分这些重复计算能不能用一个表存下来本周第二道题我就这么试过。最初想法是递归枚举所有分割点样例确实能过但看到数据范围 ( n \le 10^5 ) 就知道必须换思路。然后我再想如果已经知道前 i 个元素能分成几个上升子序列那么新元素进来该如何更新这就自然过渡到了动态规划。用暴力拿样例不是浪费时间它有两个作用一是验证你对题意的理解是否正确二是帮你找到优化的切入点。很多同学一上来就写状态转移结果样例都跑不对就是因为连“正确但不高效”的基线都没有。1.3 把递推关系写在纸上而不是只靠脑子我写 dp 题有一个原则先在纸上画格子。以背包问题为例我会画一个表格行是物品编号列是背包容量每个格子记录“考虑到前 i 个物品、容量为 j 时的最大价值”。然后手动填几个格子看看当前格子和上一行的哪个格子有关系。这个动作看起来慢其实是逼自己理解状态定义。本周踩过的一个典型坑是状态定义里“容量不超过 j”和“容量恰好为 j”的含义不同导致初始化完全不同。如果不亲手填表根本意识不到两者差别。我自己把表格画出来之后才发现第二道题如果用“恰好为 j”来定义初始化就得把 dp[0] 设为 0、其余设为负无穷否则转移会得到错误结果。所以我的建议是不要急着敲代码。哪怕你只在纸上画 3×3 的格子也比反复提交看评测结果高效得多。2. 背包类题从二维 DP 到滚动数组2.1 为什么第一感觉的贪心是错的本周第一道作业题是典型的 0-1 背包变形很多人的第一反应是“按单位价值排序优先选性价比高的”。这个思路在允许拆分物品时是对的但 0-1 背包要求整件取或不取于是贪心会失效。我举个例子你就明白了背包容量是 10A 物品体积 6、价值 8B 物品体积 5、价值 6C 物品体积 5、价值 6。按单位价值A 最高但你选了 A 之后剩下 4 容量什么也装不了总价值 8而选 B 和 C 能装下 10 容量总价值 12。这就是“局部最优不等价于全局最优”的经典反例。那用什么能保证全局最优动态规划。因为 dp 会把“容量恰好为 j 时能达到的最大价值”这个子问题全部记录下来然后再由小到大组合。这种“暴力记录所有可达状态”的思路虽然看着笨却能绕过贪心的盲区。2.2 状态定义和转移方程的完整推导设物品数量为 n背包容量为 V。第 i 件物品体积为 w[i]价值为 v[i]。定义 dp[i][j] 表示“从前 i 件物品中选总容量不超过 j 时能获得的最大价值”。转移的时候第 i 件物品只有两种可能不选dp[i][j] dp[i-1][j]选前提是 j w[i]那么 dp[i][j] dp[i-1][j-w[i]] v[i]。合起来就是for (int i 1; i n; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; if (j w[i]) { dp[i][j] max(dp[i][j], dp[i-1][j-w[i]] v[i]); } } }注意转移里用的是 dp[i-1][j-w[i]]也就是上一行的状态。这意味着第 i 件物品只被考虑一次这正好符合“每件物品只能选一次”的 0-1 背包语义。如果写成 dp[i][j-w[i]]就变成了同一件物品可以反复选那是完全背包不是这道题要的。2.3 一维化和背包体积正序倒序的本质二维 dp 空间是 ( O(nV) )本周数据范围一上来直接开二维数组会内存超限。优化方式是滚动数组把 dp 压缩成一维dp[j] 表示“容量为 j 时能取得的最大价值”。但这里有一个无数人踩过无数次的坑容量循环要倒序还是正序// 正确写法倒序 for (int i 1; i n; i) { for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }倒序的原因很简单dp[j] 的更新依赖上一轮的 dp[j-w[i]]。如果 j 从小到大扫那么 dp[j-w[i]] 可能在当前这一轮已经被更新过相当于第 i 件物品在同一个物品循环里被用了两次这就把 0-1 背包做成了完全背包。倒序能保证 dp[j-w[i]] 还没被本轮更新用的仍然是上一轮的结果。我当时第一次写就写成了正序样例输出大了不少排查了半天才反应过来。你可以把这个当成口诀记住“0-1 背包倒序完全背包正序。”但更建议你理解原理因为只有理解了才能在变了形的题目里反应过来。3. 子序列划分题LIS 的两种实现对比3.1 朴素 O(n²) 递推怎么拆本周第二道题表面是“把一个序列划分成最少几个上升子序列”但经过模型识别之后它本质上是在求最长上升子序列的长度。这个等价关系其实不直观我先说朴素做法。定义 dp[i] 表示“以第 i 个元素结尾的最长上升子序列长度”。转移时遍历所有 j i如果 a[j] a[i]就可以尝试把 a[i] 接在 a[j] 后面for (int i 1; i n; i) { dp[i] 1; for (int j 1; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } }这个做法的时间复杂度是 ( O(n^2) )本周数据范围比较温和时能过但更严格的数据会超时。我一开始就用这个朴素版本拿了个基础分然后才开始想优化。这个朴素版的关键是理解“以 i 结尾”这个约束。很多同学定义 dp[i] 时只写了“前 i 个元素的最长上升子序列长度”这样定义会导致无法转移因为新元素能不能接在后面取决于上一个元素的真实值。所以 dp 状态的设定必须携带足够的信息“结尾元素”就是那个被携带的信息。3.2 贪心维护上升序列下界朴素做法慢是因为每来一个新元素都要和前面所有元素比较一遍。优化的思路是维护一个数组 tailtail[k] 表示“长度为 k 的上升子序列中结尾元素的最小值”。为什么维护最小值因为同样长度下结尾越小将来就越容易在后面接上新的元素。这个策略是贪心的但它的正确性建立在“长度越大结尾值一定越大”的单调性上。于是可以用二分查找新元素能接在哪个位置整体复杂度降到 ( O(n \log n) )。vectorint tail; for (int x : a) { int pos lower_bound(tail.begin(), tail.end(), x) - tail.begin(); if (pos tail.size()) { tail.push_back(x); } else { tail[pos] x; } }这个代码非常短但里面藏着一个容易误解的点tail 数组里的值并不是“最长上升子序列”本身它只是记录了每个长度下可能的最小结尾。换句话说tail 数组不是答案序列长度才是答案。我刚开始学这里的时候曾经试图把 tail 数组直接输出当成子序列结果当然不对。后来我给自己写了一句备注tail 保存的是“每种长度的最佳结尾”不是“最终方案”。有了这句话再看二分逻辑就顺多了。3.3 dp 数组下标从 0 开始还是从 1 开始这是一个看起来很细节、实际上能让你调试一晚上的问题。本周我在子序列划分题里就吃过亏。如果下标从 1 开始dp[0] 可以留作空序列的占位转移里 dp[j] 1 的语义更直观。但如果下标从 0 开始dp[0] 就是第一个元素本身循环边界很容易多跑或少跑一位导致数组越界。我的经验是动态规划题统一用“下标从 1 开始”的写法在输入时把数据存到 a[1] 到 a[n]然后多申请一位数组空间。这样 dp[0] 可以用来表示“没有元素”的初始状态代码整体也更好读。不过要记住输出答案时可能涉及 n 的边界比如最后答案可能是 max(dp[1..n])而不是 dp[n]。我见过有人从 1 开始写但最后习惯性地输出 dp[n]结果漏了前面几个元素单独成段的情况。答案是去 dp 数组里取最大值不是无脑输出最后一个位置。4. 区间 DP 题合并过程的子结构4.1 dp[i][j] 表示的是什么本周第三道题的典型特征是“合并相邻两项合并会产生代价求最小总代价”。这种题的通用状态定义是dp[i][j] 表示“把区间 [i, j] 合并成一堆所需要的最小代价”。为什么区间 DP 的状态定义里必须有“区间”两个端点因为合并是相邻的你不能像普通 dp 那样只用一个递增下标 i 表示“前 i 个元素”。你必须在状态里记录“当前处理的是哪个连续区间”否则无法表达最后一次合并是哪两个相邻部分合并的。这个定义还有个隐含语义dp[i][i] 表示单个元素自己已经是一堆合并代价为 0。这就是后面所有边界条件的起点。4.2 枚举长度、左端点、断点的三重循环区间 DP 的转移方程思路是把大区间分成两个相邻的小区间分别合并再把两堆合成一堆。于是[ dp[i][j] \min_{k \in [i, j-1]} (dp[i][k] dp[k1][j] cost(i,j)) ]其中 cost(i,j) 是把两堆合并时需要付出的代价。写代码的时候最经典的循环顺序是for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost(i, j)); } } }这里最容易犯的错误是三层循环的顺序。如果你把 i 的循环写在最外层再枚举 len那么当你在计算 dp[2][4] 的时候dp[3][4] 很可能还没有被计算出来。区间 DP 的正确顺序是“先枚举区间长度再枚举起点”这样才能保证计算长区间时所有需要的短区间结果已经就绪。我自己第一次写的时候就栽了跟头外层循环用了 i结果样例错得离谱打印中间表之后才发现dp[3][4] 还是初始的 INF用它去更新 dp[1][4] 当然全是 INF。后来我把循环顺序背了下来也真正理解了“为什么必须先 len 后 i”因为 dp 的过程就是从小规模子问题向更大规模子问题递推len 就是子问题的规模。4.3 初始化无穷大的讲究区间 DP 里dp[i][j] 的初始值一般不能直接填 0因为求的是最小值如果初始值全为 0所有转移都会取到什么也不合并的 0结果还是 0显然错了。正确做法是先把整个 dp 数组填成一个大数比如0x3f3f3f3f然后把长度为 1 的区间 dp[i][i] 设为 0。这样转移过程中只有真正被计算过的区间才会得到有限值。为什么推荐0x3f3f3f3f而不是INT_MAX因为INT_MAX加一个正数会溢出变成负数导致 min 的比较结果完全错乱。这类问题在比赛中很容易出现平时养成就用0x3f3f3f3f它足够大而且两个这样的数相加还在 int 范围内不会溢出。另外一个细节如果答案要输出方案比如打印合并顺序那还需要额外开一个数组记录每个区间的最优分割点 k。本周题目没要求输出方案但如果你在练习可以顺手把它做了这对理解“记录决策点”的思路很有帮助。5. 调试记录与常见问题排查手册5.1 样例过了但提交全错的检查清单这是最让人崩溃的情况。本周我在第三道题上就遇到过样例输出完全正确提交之后却一个点都过不了。后来排查下来问题出在数组大小只开到 n没有开到 n2导致 i1 越界。我给自己整理了一份检查清单按顺序排查数组是否多开了一两位dp 下标从 1 开始数组最好开到 n5初始化是否区分了“恰好”和“不超过”这两个语义的初始化完全不同循环边界是否把 n 写成了 n-1区间 DP 里尤其容易错每一轮是否更新了 dp[i][j] 的初值为 INF如果没有上一轮的脏数据会残留是否用了 0x3f3f3f3f如果 INF 太大相加会溢出。每次提交前对照这个清单过一遍能省不少罚时。5.2 遇到 Segment Fault 多半是越界运行时报段错误第一反应不要去看什么指针问题先检查数组下标。在算法题里段错误九成是因为访问了 dp[-1]、dp[n1] 这类非法位置。本周背包题的二维转一维时我曾经把循环写成for (int j V; j 0; j--)这在 j-w[i] 小于 0 时会访问负下标吗其实不会因为我在循环里加了if (j w[i])的检查。但有人图省事直接写成j w[i]一旦 w[i] 是 0 就可能死循环或越界。所以我建议循环条件统一写j w[i]避免边界判断不一致。另外区间 DP 的 j i len - 1当 len 很大时j 可能超出 n。三层循环里一定要保证i len - 1 n再进入处理逻辑。这个 bug 我用肉眼看了半天没看出来最后还是打印 i、j、len 才定位到。5.3 内存超限空间换时间要有限度动态规划经常用空间换时间但如果空间换得太多也会带来烦恼。本周第一题如果用二维 int 数组当 n2000、V2000 时数组大小是 400 万个 int约 16 MB勉强可以接受但要是 n10000、V10000二维数组就变成 400 MB 了直接内存超限。优化手段除了滚动数组还有“用 short 存转移来源”“用 vector 动态分配”“根据数据范围选择算法”。我的习惯是做题前先估算n * V 是多少如果超过 1e7就该考虑一维优化或其他算法。不要等评测结果告诉你内存超限了才后悔没做估算。有一个实用技巧调试时可以在本地先设一个小的数据范围跑出正确结果后再改回完整范围。这样能避免因为数据量太大导致本地 IDE 卡顿也更容易观察中间数组的变化。6. 从一周作业里提炼的通用思维模板6.1 三个可复用的递推套路做完这周作业我最大的收获不是背住了三道题的解法而是总结出了三个可以复用的套路。第一个套路状态定义要带上“题目要求的所有约束”。背包题的状态带容量 jLIS 题的状态带结尾下标 i区间 DP 的状态带左右端点。当你想不清楚状态怎么设时就问自己当前这一步哪些信息会影响后面的决策把这些信息写进状态基本上不会错。第二个套路转移就是“枚举当前元素的所有行为”。第 i 件物品选还是不选第 i 个元素放在已有子序列后面还是新开一段区间最后一次合并的分割点在哪里你只需要把所有可能性写出来取 max 或 min转移方程就出来了。第三个套路初始化一定要和状态定义匹配。定义“不超过 j”初始化全 0 没问题定义“恰好为 j”初始化就要区分可达和不可达。这个细节直接决定程序对不对而且靠肉眼极难发现。6.2 下一步可以怎么训练如果你也刚做完第九周作业我建议你做两件事。第一把这三道题分别用两种写法实现一遍比如背包题分别写二维和一维子序列题分别写朴素约等于写一版。不要觉得重复没有意义写第二遍的时候你会更清楚地看到循环顺序和初始化对结果的影响。第二试着把题目的条件改一改看看答案会发生什么变化。比如把“每件物品只能选一次”改成“每件物品能选无限次”背包的一维循环顺序会如何变把上升子序列里的“严格上升”改成“非严格上升”二分查找应该用 lower_bound 还是 upper_bound这样改着玩比连刷十道同样套路的题更锻炼理解力。我个人的体会是动态规划不是“背模板”而是“把大问题拆成小问题、小问题之间用递推连接”的思维方式。第九周作业题恰好把这个过程完整地展示了一遍。哪怕你已经 AC 了这些题也值得回头再看一眼自己写的第一版代码看看哪里还能优化、哪里差点翻车。那些不起眼的坑才是真正让你成长的地方。