1. 线性DP的模型认知从“为什么”开始1.1 状态设计的基本套路动态规划学到现在你已经见过背包、区间、树形这些经典模型。到了part11我们回头把线性DP这个最朴素也最容易被低估的模型重新梳理一遍。很多人在洛谷刷题时有个错觉线性DP不就是一维数组扫一遍吗真到比赛和工程里线性DP反而是出错率最高的模型。因为它的坑不在转移方程有多难写而在状态设计是否真正覆盖了所有决策路径。我习惯把线性DP的状态设计拆成三个问题你在描述“谁”对象在哪个“位置”阶段以及手里有什么“信息”约束。比如最长上升子序列对象是序列元素位置是下标i信息是“以a[i]结尾”。这三个要素缺一个状态就是残缺的。很多新手写状态时只写“dp[i]表示前i个元素的最优解”这就是典型的信息丢失——前i个元素的最优解如果不知道结尾是谁就没办法判断下一个元素能否接上。这类错误在刷洛谷题单时特别常见大家写题解喜欢用“dp[i]表示以i结尾”却不解释为什么不能只用“前i个”。另一个容易忽略的点是线性DP的“线性”不只是下标一维还包含“阶段的有序性”。你必须保证状态转移是单向的、无环的。换句话说计算dp[i]时用到的所有子状态dp[j]j i都必须已经算完。这个特性决定了线性DP天然适合自底向上迭代而不是像树形DP那样递归。理解这一点对后面优化复杂度非常关键——你能清楚地知道哪些维度的状态可以滚动掉哪些不能。1.2 转移方程的三要素与常见陷阱我把一个合格的转移方程拆成三部分决策集合、收益函数、约束条件。以最长公共子序列LCS为例状态dp[i][j]表示“a串前i个字符与b串前j个字符的最长公共子序列长度”。决策集合是“a[i]是否与b[j]匹配”收益函数是匹配则dp[i-1][j-1]1约束条件是a[i]b[j]才能匹配。这三个要素缺一不可缺少决策枚举就变成贪心缺少约束就变成无限制组合。实际做题时最常见的失败模式是“强行压缩状态”。我见过有人把LCS的状态压成一维来优化空间结果转移时依赖的dp[i-1][j]和dp[i][j-1]被覆盖答案直接错乱。压缩维度不是不可以但你必须清楚每个状态在迭代中的存活周期。滚动数组的正确做法是保留下标j的完整维度只滚动i这一维这样dp[j]表示上一轮的结果dp[j-1]在本轮已经更新两者都还有效。如果你连j也省掉那恭喜你基本等于亲手把子问题信息抹掉了。还有一类陷阱隐藏在“初始化”里。线性DP的初始化不是简单地把dp[0]设成0就完事。以最大子段和为例dp[i]表示以第i个元素结尾的最大子段和初始化要求dp[1] a[1]而不是从dp[0]开始递推否则负数数组会得到一个错误的空段答案。初始化本质上是定义“最小子问题的正确答案”它决定了整个递推的起点是否正确。每次写转移方程前先问自己一句dp[0]或dp[1]的物理意义是什么它的值应该是多少1.3 多阶段决策的线性视角线性DP本质上解决的是“多阶段决策问题”的最简单形态阶段天然有序每阶段做一个决策决策影响后续阶段的可选空间。车辆动态规划问题就是一个典型代表——车辆在一条线路上行驶每个站点都有装卸货决策阶段的推进就是车辆位置的变化。这类问题在教材里常被归为“最短路”或“调度”骨子里却是个线性DP状态是当前站点和剩余运力决策是装还是不装、走还是停。把多阶段决策塞进线性DP的关键是“显式定义阶段的推进规则”。换句话说你要能回答从阶段i到阶段i1哪个量变了哪个量不变改变了的是状态里的哪一项如果这个量不在状态里转移方程就写不出来。比如车辆问题中如果状态只记录“当前站点编号”却没有记录“剩余装载量”那么到下一站能否装货就无法判断。这就是我反复强调状态三要素的原因——每一项都有它的物理意义和存在必要性。有了这个视角你会发现线性DP其实是一种“建模方法论”而不是模板。它教你的是把过程拆成有序阶段、定义每阶段的完整快照、找出相邻阶段状态的关系。这套方法论学会了洛谷题单里的各种变体题、工程里的调度问题、甚至一些看似和DP无关的最优化问题你都能一眼看穿它的递推结构。2. 洛谷经典题单实战拆解从推导到AC2.1 最长上升子序列的完整推导洛谷动态规划题单里最长上升子序列LIS几乎是必刷的第一道线性DP。题目描述很简单给定一个序列求最长的严格上升子序列长度。很多人的第一版代码是这样的#include bits/stdc.h using namespace std; const int MAXN 5005; int a[MAXN], dp[MAXN]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; int ans 0; 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); } } ans max(ans, dp[i]); } cout ans endl; return 0; }这段代码的核心逻辑是每个位置i至少能单独构成一个长度为1的子序列所以dp[i]初始化为1然后枚举所有在i之前的位置j如果a[j] a[i]说明i可以接到j后面此时dp[i]的候选值就是dp[j] 1。这个O(n²)的做法在n ≤ 5000时可以通过因为5000²等于2500万次运算C在1秒内能轻松跑完。我在讲解这个题时一定会强调dp[i]的状态含义是“以a[i]结尾的LIS长度”而不是“前i个元素中的LIS长度”。这两者的差别就是AC和WA的分界线。如果你定义成后者转移时不知道子序列的结尾元素就没法判断“是否严格上升”这个约束条件整个递推链就断了。我自己最初学的时候就在这里栽过跟头写出的代码样例能过一提交就WA一半排查半天才发现状态定义出错。2.2 最长公共子序列与方案构造LCS是线性DP里的另一个高频考点。洛谷题单一般安排在LIS之后因为它的状态变成了二维转移的书写复杂度上了一个台阶。状态定义是dp[i][j]表示“a串前i个字符与b串前j个字符的最长公共子序列长度”。转移分两种情况如果a[i] b[j]说明这两个字符能匹配那么dp[i][j] dp[i-1][j-1] 1如果不相等就取max(dp[i-1][j], dp[i][j-1])也就是跳过a串的一个字符或跳过b串的一个字符看哪种方案保留的公共部分更长。for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i] b[j]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } }这里有一个我在教学中反复强调的点为什么a[i] b[j]时不需要再比较dp[i-1][j]和dp[i][j-1]因为dp[i-1][j-1]是“都要么用了前i-1和前j-1个字符的答案此时a[i]和b[j]都还没用上。匹配这两个字符后长度至少不会比跳过它们更差——严格来说dp[i-1][j]和dp[i][j-1]的最优解也建立在dp[i-1][j-1]之上所以直接取dp[i-1][j-1]1不会遗漏更优方案。这一点想通了LCS的转移方程才算真正理解而不是背下来的。如果题目要求输出具体的公共子序列就需要在DP过程中记录决策来源。开一个pre[i][j]数组标记当前状态是从哪里转移来的来自dp[i-1][j-1]1记为1来自dp[i-1][j]记为2来自dp[i][j-1]记为3。最后从dp[n][m]沿着pre数组回溯遇到标记为1的位置就把对应字符加入答案。这个“记录决策来源 回溯”的思路在动态规划里通用性很强后面做编辑距离、背包方案计数都会用到。2.3 从题单看线性DP的出题套路刷洛谷动态规划题单时你会发现一个规律线性DP的题目看起来千变万化但核心只有两类——一类是“序列上的选择问题”LIS、最大子段和、最长接龙另一类是“两个序列的匹配问题”LCS、编辑距离。前者是一维状态后者是二维状态。出题人会在这些基础上叠加限制条件比如“必须连续”、“不能相邻”、“有重量限制”本质都是在状态定义里增加一个维度或者在转移里增加一个判断条件。比如经典的最大子段和问题表面上是“求一段连续区间和的最大值”状态dp[i]表示“以第i个元素结尾的最大子段和”转移只有两个选择把a[i]接到前面的段上dp[i-1] a[i]或者从a[i]重新开始a[i]。整个问题的关键在于“连续”这个约束体现在状态“以i结尾”上因为只有以i结尾才能保证下一项i1接上时区间仍然连续。这就是线性DP的基本功把题目里的每一个限制条件翻译成状态的一个属性或转移的一个分支。还有一个常见的进阶套路是“把线性DP变成图上DP”。比如最长上升子序列的O(n log n)优化本质上是把每个元素看成图中的节点在“末尾值最小”的意义下维护一个单调数组。理解到这个层面你就不需要背模板而是能自己推导出来。我一直鼓励读者在刷题单时不要只满足于AC多想想“为什么状态要这么定义”“如果不这么定义会怎样”这样才能把一个题变成一类题。3. 车辆动态规划问题线性DP的工程化落地3.1 问题建模与约束分析车辆调度问题Vehicle Scheduling Problem是动态规划在工程里最常见的应用形式之一也直接对应热搜词中的“车辆动态规划问题”。我们从一个最典型的场景入手一辆配送车从起点出发依次经过n个站点每个站点有若干货物需要装载但车辆有最大载重量限制。目标是选择哪些站点的货物装车使得总装载价值最大。这个问题的基础版本可以建模为dp[i][w]表示“前i个站点中做出选择后总重量恰好为w时的最大总价值”。这是个0/1背包的线性变体但注意它的“线性”体现在站点顺序上——每到一个站点只有装和/or not装这个决策而决策与前面站点的最佳选择组合成最优。如果不考虑货物重量问题就退化成“每个站点选或不选使价值最大”的简单贪心一旦加入重量约束就必须用DP记录所有可能的重量状态。我用生活类比来解释这就像一个旅行者每到一个景点都可以买纪念品但行李箱容量有限他需要在每个景点决定“买”还是“不买”目标是让带回家的纪念品总价值最高。旅行者每到一个新景点时的状态是“行李箱里已经占了多少空间”这正是dp[i][w]中w的物理意义。如果没有这一维游客就没法判断下一个纪念品是否塞得下决策就无从谈起。建模过程中最容易被漏掉的约束有三个站点顺序是否严格能不能回头、货物是否可拆分0/1还是分数背包、车辆是否有容量上限之外的体积限制。这些看起来是题目描述里的细节实际上每一个都会改变状态定义。我在实际项目中见过有人把“车辆顺序必须按站点编号”这个条件漏掉结果模型解出来发现车辆乱序行驶和实际路线完全对不上。3.2 状态压缩与复杂度优化车辆DP虽然从一维扩展到了二维但n个站点、w的重量上限动辄上万两层循环O(nw)就已经是千万级的运算量。实际的车辆调度里站点数量可能更大这时候就需要针对具体场景做状态压缩。我在工程里最常用的是滚动数组vectorint dp(maxWeight 1, 0); for (int i 1; i n; i) { for (int w maxWeight; w weight[i]; w--) { dp[w] max(dp[w], dp[w - weight[i]] value[i]); } }这里有一个初学者经常踩的坑第二层循环必须倒序遍历重量。原因是如果正序遍历dp[w - weight[i]]在当前轮次已经被更新过相当于同一个站点的货物被装了多次这与“每个站点最多装一次”的约束冲突。倒序遍历保证每次用到的dp[w - weight[i]]都还是上一轮的结果。这个细节在我见过的背包类代码错误里占据了相当高的比例。如果重量上限特别大但每个站点的货物只有有限种重量组合可以先对货物按重量分组再用单调队列优化多重背包的转移。这个优化稍微复杂一些但核心思想仍然没有脱离线性DP的框架阶段按站点推进每个阶段维护一张“重量到最大价值”的表。当重量维度很大时还可以考虑将所有站点的货物价值与重量做一个性价比排序先装价值密度高的货物做初始解再用DP做精确优化工程上常常收益明显。3.3 典型场景演练与仿真我拿一个简化案例带大家走一遍完整流程。假设配送车最大载重10吨有5个站点每个站点的货物重量与价值如下表站点重量吨价值千元134245356423511用滚动数组模拟一遍。初始dp[0] 0其余为负无穷表示不可达。处理站点1重量3价值4倒序遍历dp[3]从不可达变成4此时dp数组在重量3的位置有值。处理站点2重量4价值5dp[4]5dp[7]max(dp[7], dp[3]5)459。处理站点3重量5价值6dp[5]6dp[8]dp[3]610dp[9]dp[4]611。处理站点4重量2价值3dp[2]3dp[5]max(6, dp[3]37)7dp[6]dp[4]38。处理站点5重量1价值1dp[1]1dp[3]4dp[4]max(5, dp[3]15)5dp[6]max(8, dp[5]18)8。最终答案是dp[10]或所有dp[w]中的最大值。手动模拟一遍就会发现滚动数组的倒序遍历到底在保护什么——它保证了每个站点只被考虑一次。如果你正序遍历站点1的货物会被反复装进背包得出一个远超实际价值上限的答案。模拟完这个过程我认为你对“为什么倒序”这个问题就不会再有疑惑了。4. 调试技巧与常见错误实录4.1 边界与初始化的坑动态规划题目的WA十有八九出在初始化和边界上。我举一个常见的例子LIS问题中如果你把dp数组初始化为0而序列第一个元素是负数那么dp[1]会保持0后续所有转移都从这个错误起点出发答案就偏小。正确的初始化是dp[i] 1每个元素至少可以独自构成长度为1的子序列然后从i1开始递推。这个“1”就是最小子问题的正确答案——只有它对了递推链才会对。另一个边界问题是下标越界。在二维DP中dp[i-1][j-1]在i1或j1时会访问到下标0——这通常是合法的只要你的数组从0开始分配且dp[0][]和dp[][0]被正确初始化为0。但如果数组开小了或者在转移前忘记判断j-1是否合法就越界访问轻则答案错误重则运行时崩溃。我的习惯是数组一律开成MAXN5且全局变量默认清零这样边界处理会宽松很多。4.2 滚动数组的踩坑经验滚动数组能省内存但代价是代码可读性下降、错误风险上升。我踩过最典型的坑是状态压缩后忘记保留“当前阶段需要的新值”和“上一阶段的老值”结果在同一个循环里既读又写导致状态互相污染。比如LCS的滚动数组写法for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i] b[j]) dp[j] prev[j-1] 1; else dp[j] max(prev[j], dp[j-1]); } }这里prev[j-1]必须保存的是上一轮i的dp[j-1]值而不是当前轮已经更新的dp[j-1]。所以每轮外层循环开始时你要用一个变量记录本轮尚未被覆盖的“上一轮值”或者用prev数组整体保存。我在最开始写错时调试了很久才发现是“新旧值混用”后来总结出一个铁律滚动数组里凡是转移用到的“旧值”要么单独保存要么在更新前先暂存到临时变量。4.3 状态定义错误的典型信号状态定义错了最明显的信号是“样例能过、测试点大面积WA”。具体表现有两种一种是答案总是比预期值小说明状态遗漏了某些决策路径另一种是答案出现非整数或越界说明转移方程中某个分支的状态含义不对。我建议你在写转移方程之前先用自己的话把dp[i][j]的物理意义写下来然后问自己三个问题这个状态对应原问题的哪个子问题它包含哪些信息这些信息是否足以支持所有合法的后续决策如果这三个问题有一个回答不出来状态定义基本就有问题。比如在接龙类题目里有人定义dp[i]为“前i个字符串能构成的最长接龙长度”但没定义“最后一个字符串是谁”导致转移时无法判断当前字符串能不能接上去。这时候只要把状态改为“以第i个字符串结尾的最长接龙长度”问题立刻迎刃而解。5. 优化进阶从O(n²)到O(n log n)5.1 二分优化LIS的原理与实现当n达到10⁵甚至10⁶级别O(n²)的LIS算法必然超时。标准优化思路不再保留具体某个dp[i]的长度而是维护一个数组d[]其中d[k]表示“长度为k的所有上升子序列中末尾元素的最小值”。这个数组是单调递增的所以对于每个新元素a[i]可以用二分查找找到“第一个大于等于a[i]的位置pos”然后把d[pos]更新为a[i]。最终答案就是d数组的有效长度。vectorint d; for (int i 1; i n; i) { auto it lower_bound(d.begin(), d.end(), a[i]); if (it d.end()) d.push_back(a[i]); else *it a[i]; } cout d.size() endl;为什么这个优化是正确的核心在于一个贪心性质对于相同长度的子序列末尾元素越小后面越容易接上更长的上升序列。所以维护“每个长度的最小末尾值”是最优的。每次用a[i]去替换第一个不小于它的位置相当于“在保证上升性质的前提下尽量让末尾变小”。这个思路和“最长上升子序列本身的DP”之间的关系可以用一个比喻来理解d[k]就像是“这个长度档次的门槛”门槛越低越容易吸引新元素跨进来拉长序列。5.2 状态维度压缩技巧除了LIS的二分优化线性DP的优化还有一个大方向——状态维度压缩。常见的压缩方法有三种滚动数组省空间、单调队列省时间、斜率优化省时间。其中单调队列优化最经典的应用是“定长滑动窗口最大值类DP”比如一些带长度限制的线性DP问题转移时需要在滑动窗口内取最值。这时如果朴素枚举窗口内所有状态复杂度O(nk)用单调队列维护窗口内状态的最值后复杂度降到O(n)。我这里要提醒一句单调队列优化对DP的单调性有要求不能乱套用。它适用于转移方程形如dp[i] max(dp[j] cost(i, j))且j的取值范围随i单调移动的场景。如果窗口不是单调右移就不能直接用单调队列。所以每次看到“区间约束的线性DP”先判断j的取值范围是否是滑动窗口再做优化否则容易画蛇添足。斜率优化则更适合形如dp[i] min(dp[j] (a[i] - a[j])²)这类带平方项的问题核心思想是把状态间的转移看成直线求交用凸包维护一个下凸壳每次转移时在凸壳上二分或找交点。它的原理和代码实现都更复杂但一旦掌握很多看似不可能的大数据范围线性DP都能解。我在实际比赛中见过不少题目O(n²)能过50%加斜率优化直接AC。不过说实话斜率优化对数学推导能力要求比较高我建议先把前面的所有优化都弄熟练了再啃这一块。最后再分享一个小技巧不管是刷洛谷动态规划题单还是做工程里的车辆调度问题拿到题先别急着写代码花两分钟在纸上画一画状态转移图标清楚每个状态的来源和去向。这个习惯帮我省下的调试时间比我写的任何代码都值钱。动态规划就是这样状态定义对了转移方程写对了整个题的难度就下降了一大半。 线性DP完全指南：状态设计、转移方程与优化实战
1. 线性DP的模型认知从“为什么”开始1.1 状态设计的基本套路动态规划学到现在你已经见过背包、区间、树形这些经典模型。到了part11我们回头把线性DP这个最朴素也最容易被低估的模型重新梳理一遍。很多人在洛谷刷题时有个错觉线性DP不就是一维数组扫一遍吗真到比赛和工程里线性DP反而是出错率最高的模型。因为它的坑不在转移方程有多难写而在状态设计是否真正覆盖了所有决策路径。我习惯把线性DP的状态设计拆成三个问题你在描述“谁”对象在哪个“位置”阶段以及手里有什么“信息”约束。比如最长上升子序列对象是序列元素位置是下标i信息是“以a[i]结尾”。这三个要素缺一个状态就是残缺的。很多新手写状态时只写“dp[i]表示前i个元素的最优解”这就是典型的信息丢失——前i个元素的最优解如果不知道结尾是谁就没办法判断下一个元素能否接上。这类错误在刷洛谷题单时特别常见大家写题解喜欢用“dp[i]表示以i结尾”却不解释为什么不能只用“前i个”。另一个容易忽略的点是线性DP的“线性”不只是下标一维还包含“阶段的有序性”。你必须保证状态转移是单向的、无环的。换句话说计算dp[i]时用到的所有子状态dp[j]j i都必须已经算完。这个特性决定了线性DP天然适合自底向上迭代而不是像树形DP那样递归。理解这一点对后面优化复杂度非常关键——你能清楚地知道哪些维度的状态可以滚动掉哪些不能。1.2 转移方程的三要素与常见陷阱我把一个合格的转移方程拆成三部分决策集合、收益函数、约束条件。以最长公共子序列LCS为例状态dp[i][j]表示“a串前i个字符与b串前j个字符的最长公共子序列长度”。决策集合是“a[i]是否与b[j]匹配”收益函数是匹配则dp[i-1][j-1]1约束条件是a[i]b[j]才能匹配。这三个要素缺一不可缺少决策枚举就变成贪心缺少约束就变成无限制组合。实际做题时最常见的失败模式是“强行压缩状态”。我见过有人把LCS的状态压成一维来优化空间结果转移时依赖的dp[i-1][j]和dp[i][j-1]被覆盖答案直接错乱。压缩维度不是不可以但你必须清楚每个状态在迭代中的存活周期。滚动数组的正确做法是保留下标j的完整维度只滚动i这一维这样dp[j]表示上一轮的结果dp[j-1]在本轮已经更新两者都还有效。如果你连j也省掉那恭喜你基本等于亲手把子问题信息抹掉了。还有一类陷阱隐藏在“初始化”里。线性DP的初始化不是简单地把dp[0]设成0就完事。以最大子段和为例dp[i]表示以第i个元素结尾的最大子段和初始化要求dp[1] a[1]而不是从dp[0]开始递推否则负数数组会得到一个错误的空段答案。初始化本质上是定义“最小子问题的正确答案”它决定了整个递推的起点是否正确。每次写转移方程前先问自己一句dp[0]或dp[1]的物理意义是什么它的值应该是多少1.3 多阶段决策的线性视角线性DP本质上解决的是“多阶段决策问题”的最简单形态阶段天然有序每阶段做一个决策决策影响后续阶段的可选空间。车辆动态规划问题就是一个典型代表——车辆在一条线路上行驶每个站点都有装卸货决策阶段的推进就是车辆位置的变化。这类问题在教材里常被归为“最短路”或“调度”骨子里却是个线性DP状态是当前站点和剩余运力决策是装还是不装、走还是停。把多阶段决策塞进线性DP的关键是“显式定义阶段的推进规则”。换句话说你要能回答从阶段i到阶段i1哪个量变了哪个量不变改变了的是状态里的哪一项如果这个量不在状态里转移方程就写不出来。比如车辆问题中如果状态只记录“当前站点编号”却没有记录“剩余装载量”那么到下一站能否装货就无法判断。这就是我反复强调状态三要素的原因——每一项都有它的物理意义和存在必要性。有了这个视角你会发现线性DP其实是一种“建模方法论”而不是模板。它教你的是把过程拆成有序阶段、定义每阶段的完整快照、找出相邻阶段状态的关系。这套方法论学会了洛谷题单里的各种变体题、工程里的调度问题、甚至一些看似和DP无关的最优化问题你都能一眼看穿它的递推结构。2. 洛谷经典题单实战拆解从推导到AC2.1 最长上升子序列的完整推导洛谷动态规划题单里最长上升子序列LIS几乎是必刷的第一道线性DP。题目描述很简单给定一个序列求最长的严格上升子序列长度。很多人的第一版代码是这样的#include bits/stdc.h using namespace std; const int MAXN 5005; int a[MAXN], dp[MAXN]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; int ans 0; 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); } } ans max(ans, dp[i]); } cout ans endl; return 0; }这段代码的核心逻辑是每个位置i至少能单独构成一个长度为1的子序列所以dp[i]初始化为1然后枚举所有在i之前的位置j如果a[j] a[i]说明i可以接到j后面此时dp[i]的候选值就是dp[j] 1。这个O(n²)的做法在n ≤ 5000时可以通过因为5000²等于2500万次运算C在1秒内能轻松跑完。我在讲解这个题时一定会强调dp[i]的状态含义是“以a[i]结尾的LIS长度”而不是“前i个元素中的LIS长度”。这两者的差别就是AC和WA的分界线。如果你定义成后者转移时不知道子序列的结尾元素就没法判断“是否严格上升”这个约束条件整个递推链就断了。我自己最初学的时候就在这里栽过跟头写出的代码样例能过一提交就WA一半排查半天才发现状态定义出错。2.2 最长公共子序列与方案构造LCS是线性DP里的另一个高频考点。洛谷题单一般安排在LIS之后因为它的状态变成了二维转移的书写复杂度上了一个台阶。状态定义是dp[i][j]表示“a串前i个字符与b串前j个字符的最长公共子序列长度”。转移分两种情况如果a[i] b[j]说明这两个字符能匹配那么dp[i][j] dp[i-1][j-1] 1如果不相等就取max(dp[i-1][j], dp[i][j-1])也就是跳过a串的一个字符或跳过b串的一个字符看哪种方案保留的公共部分更长。for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i] b[j]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } }这里有一个我在教学中反复强调的点为什么a[i] b[j]时不需要再比较dp[i-1][j]和dp[i][j-1]因为dp[i-1][j-1]是“都要么用了前i-1和前j-1个字符的答案此时a[i]和b[j]都还没用上。匹配这两个字符后长度至少不会比跳过它们更差——严格来说dp[i-1][j]和dp[i][j-1]的最优解也建立在dp[i-1][j-1]之上所以直接取dp[i-1][j-1]1不会遗漏更优方案。这一点想通了LCS的转移方程才算真正理解而不是背下来的。如果题目要求输出具体的公共子序列就需要在DP过程中记录决策来源。开一个pre[i][j]数组标记当前状态是从哪里转移来的来自dp[i-1][j-1]1记为1来自dp[i-1][j]记为2来自dp[i][j-1]记为3。最后从dp[n][m]沿着pre数组回溯遇到标记为1的位置就把对应字符加入答案。这个“记录决策来源 回溯”的思路在动态规划里通用性很强后面做编辑距离、背包方案计数都会用到。2.3 从题单看线性DP的出题套路刷洛谷动态规划题单时你会发现一个规律线性DP的题目看起来千变万化但核心只有两类——一类是“序列上的选择问题”LIS、最大子段和、最长接龙另一类是“两个序列的匹配问题”LCS、编辑距离。前者是一维状态后者是二维状态。出题人会在这些基础上叠加限制条件比如“必须连续”、“不能相邻”、“有重量限制”本质都是在状态定义里增加一个维度或者在转移里增加一个判断条件。比如经典的最大子段和问题表面上是“求一段连续区间和的最大值”状态dp[i]表示“以第i个元素结尾的最大子段和”转移只有两个选择把a[i]接到前面的段上dp[i-1] a[i]或者从a[i]重新开始a[i]。整个问题的关键在于“连续”这个约束体现在状态“以i结尾”上因为只有以i结尾才能保证下一项i1接上时区间仍然连续。这就是线性DP的基本功把题目里的每一个限制条件翻译成状态的一个属性或转移的一个分支。还有一个常见的进阶套路是“把线性DP变成图上DP”。比如最长上升子序列的O(n log n)优化本质上是把每个元素看成图中的节点在“末尾值最小”的意义下维护一个单调数组。理解到这个层面你就不需要背模板而是能自己推导出来。我一直鼓励读者在刷题单时不要只满足于AC多想想“为什么状态要这么定义”“如果不这么定义会怎样”这样才能把一个题变成一类题。3. 车辆动态规划问题线性DP的工程化落地3.1 问题建模与约束分析车辆调度问题Vehicle Scheduling Problem是动态规划在工程里最常见的应用形式之一也直接对应热搜词中的“车辆动态规划问题”。我们从一个最典型的场景入手一辆配送车从起点出发依次经过n个站点每个站点有若干货物需要装载但车辆有最大载重量限制。目标是选择哪些站点的货物装车使得总装载价值最大。这个问题的基础版本可以建模为dp[i][w]表示“前i个站点中做出选择后总重量恰好为w时的最大总价值”。这是个0/1背包的线性变体但注意它的“线性”体现在站点顺序上——每到一个站点只有装和/or not装这个决策而决策与前面站点的最佳选择组合成最优。如果不考虑货物重量问题就退化成“每个站点选或不选使价值最大”的简单贪心一旦加入重量约束就必须用DP记录所有可能的重量状态。我用生活类比来解释这就像一个旅行者每到一个景点都可以买纪念品但行李箱容量有限他需要在每个景点决定“买”还是“不买”目标是让带回家的纪念品总价值最高。旅行者每到一个新景点时的状态是“行李箱里已经占了多少空间”这正是dp[i][w]中w的物理意义。如果没有这一维游客就没法判断下一个纪念品是否塞得下决策就无从谈起。建模过程中最容易被漏掉的约束有三个站点顺序是否严格能不能回头、货物是否可拆分0/1还是分数背包、车辆是否有容量上限之外的体积限制。这些看起来是题目描述里的细节实际上每一个都会改变状态定义。我在实际项目中见过有人把“车辆顺序必须按站点编号”这个条件漏掉结果模型解出来发现车辆乱序行驶和实际路线完全对不上。3.2 状态压缩与复杂度优化车辆DP虽然从一维扩展到了二维但n个站点、w的重量上限动辄上万两层循环O(nw)就已经是千万级的运算量。实际的车辆调度里站点数量可能更大这时候就需要针对具体场景做状态压缩。我在工程里最常用的是滚动数组vectorint dp(maxWeight 1, 0); for (int i 1; i n; i) { for (int w maxWeight; w weight[i]; w--) { dp[w] max(dp[w], dp[w - weight[i]] value[i]); } }这里有一个初学者经常踩的坑第二层循环必须倒序遍历重量。原因是如果正序遍历dp[w - weight[i]]在当前轮次已经被更新过相当于同一个站点的货物被装了多次这与“每个站点最多装一次”的约束冲突。倒序遍历保证每次用到的dp[w - weight[i]]都还是上一轮的结果。这个细节在我见过的背包类代码错误里占据了相当高的比例。如果重量上限特别大但每个站点的货物只有有限种重量组合可以先对货物按重量分组再用单调队列优化多重背包的转移。这个优化稍微复杂一些但核心思想仍然没有脱离线性DP的框架阶段按站点推进每个阶段维护一张“重量到最大价值”的表。当重量维度很大时还可以考虑将所有站点的货物价值与重量做一个性价比排序先装价值密度高的货物做初始解再用DP做精确优化工程上常常收益明显。3.3 典型场景演练与仿真我拿一个简化案例带大家走一遍完整流程。假设配送车最大载重10吨有5个站点每个站点的货物重量与价值如下表站点重量吨价值千元134245356423511用滚动数组模拟一遍。初始dp[0] 0其余为负无穷表示不可达。处理站点1重量3价值4倒序遍历dp[3]从不可达变成4此时dp数组在重量3的位置有值。处理站点2重量4价值5dp[4]5dp[7]max(dp[7], dp[3]5)459。处理站点3重量5价值6dp[5]6dp[8]dp[3]610dp[9]dp[4]611。处理站点4重量2价值3dp[2]3dp[5]max(6, dp[3]37)7dp[6]dp[4]38。处理站点5重量1价值1dp[1]1dp[3]4dp[4]max(5, dp[3]15)5dp[6]max(8, dp[5]18)8。最终答案是dp[10]或所有dp[w]中的最大值。手动模拟一遍就会发现滚动数组的倒序遍历到底在保护什么——它保证了每个站点只被考虑一次。如果你正序遍历站点1的货物会被反复装进背包得出一个远超实际价值上限的答案。模拟完这个过程我认为你对“为什么倒序”这个问题就不会再有疑惑了。4. 调试技巧与常见错误实录4.1 边界与初始化的坑动态规划题目的WA十有八九出在初始化和边界上。我举一个常见的例子LIS问题中如果你把dp数组初始化为0而序列第一个元素是负数那么dp[1]会保持0后续所有转移都从这个错误起点出发答案就偏小。正确的初始化是dp[i] 1每个元素至少可以独自构成长度为1的子序列然后从i1开始递推。这个“1”就是最小子问题的正确答案——只有它对了递推链才会对。另一个边界问题是下标越界。在二维DP中dp[i-1][j-1]在i1或j1时会访问到下标0——这通常是合法的只要你的数组从0开始分配且dp[0][]和dp[][0]被正确初始化为0。但如果数组开小了或者在转移前忘记判断j-1是否合法就越界访问轻则答案错误重则运行时崩溃。我的习惯是数组一律开成MAXN5且全局变量默认清零这样边界处理会宽松很多。4.2 滚动数组的踩坑经验滚动数组能省内存但代价是代码可读性下降、错误风险上升。我踩过最典型的坑是状态压缩后忘记保留“当前阶段需要的新值”和“上一阶段的老值”结果在同一个循环里既读又写导致状态互相污染。比如LCS的滚动数组写法for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i] b[j]) dp[j] prev[j-1] 1; else dp[j] max(prev[j], dp[j-1]); } }这里prev[j-1]必须保存的是上一轮i的dp[j-1]值而不是当前轮已经更新的dp[j-1]。所以每轮外层循环开始时你要用一个变量记录本轮尚未被覆盖的“上一轮值”或者用prev数组整体保存。我在最开始写错时调试了很久才发现是“新旧值混用”后来总结出一个铁律滚动数组里凡是转移用到的“旧值”要么单独保存要么在更新前先暂存到临时变量。4.3 状态定义错误的典型信号状态定义错了最明显的信号是“样例能过、测试点大面积WA”。具体表现有两种一种是答案总是比预期值小说明状态遗漏了某些决策路径另一种是答案出现非整数或越界说明转移方程中某个分支的状态含义不对。我建议你在写转移方程之前先用自己的话把dp[i][j]的物理意义写下来然后问自己三个问题这个状态对应原问题的哪个子问题它包含哪些信息这些信息是否足以支持所有合法的后续决策如果这三个问题有一个回答不出来状态定义基本就有问题。比如在接龙类题目里有人定义dp[i]为“前i个字符串能构成的最长接龙长度”但没定义“最后一个字符串是谁”导致转移时无法判断当前字符串能不能接上去。这时候只要把状态改为“以第i个字符串结尾的最长接龙长度”问题立刻迎刃而解。5. 优化进阶从O(n²)到O(n log n)5.1 二分优化LIS的原理与实现当n达到10⁵甚至10⁶级别O(n²)的LIS算法必然超时。标准优化思路不再保留具体某个dp[i]的长度而是维护一个数组d[]其中d[k]表示“长度为k的所有上升子序列中末尾元素的最小值”。这个数组是单调递增的所以对于每个新元素a[i]可以用二分查找找到“第一个大于等于a[i]的位置pos”然后把d[pos]更新为a[i]。最终答案就是d数组的有效长度。vectorint d; for (int i 1; i n; i) { auto it lower_bound(d.begin(), d.end(), a[i]); if (it d.end()) d.push_back(a[i]); else *it a[i]; } cout d.size() endl;为什么这个优化是正确的核心在于一个贪心性质对于相同长度的子序列末尾元素越小后面越容易接上更长的上升序列。所以维护“每个长度的最小末尾值”是最优的。每次用a[i]去替换第一个不小于它的位置相当于“在保证上升性质的前提下尽量让末尾变小”。这个思路和“最长上升子序列本身的DP”之间的关系可以用一个比喻来理解d[k]就像是“这个长度档次的门槛”门槛越低越容易吸引新元素跨进来拉长序列。5.2 状态维度压缩技巧除了LIS的二分优化线性DP的优化还有一个大方向——状态维度压缩。常见的压缩方法有三种滚动数组省空间、单调队列省时间、斜率优化省时间。其中单调队列优化最经典的应用是“定长滑动窗口最大值类DP”比如一些带长度限制的线性DP问题转移时需要在滑动窗口内取最值。这时如果朴素枚举窗口内所有状态复杂度O(nk)用单调队列维护窗口内状态的最值后复杂度降到O(n)。我这里要提醒一句单调队列优化对DP的单调性有要求不能乱套用。它适用于转移方程形如dp[i] max(dp[j] cost(i, j))且j的取值范围随i单调移动的场景。如果窗口不是单调右移就不能直接用单调队列。所以每次看到“区间约束的线性DP”先判断j的取值范围是否是滑动窗口再做优化否则容易画蛇添足。斜率优化则更适合形如dp[i] min(dp[j] (a[i] - a[j])²)这类带平方项的问题核心思想是把状态间的转移看成直线求交用凸包维护一个下凸壳每次转移时在凸壳上二分或找交点。它的原理和代码实现都更复杂但一旦掌握很多看似不可能的大数据范围线性DP都能解。我在实际比赛中见过不少题目O(n²)能过50%加斜率优化直接AC。不过说实话斜率优化对数学推导能力要求比较高我建议先把前面的所有优化都弄熟练了再啃这一块。最后再分享一个小技巧不管是刷洛谷动态规划题单还是做工程里的车辆调度问题拿到题先别急着写代码花两分钟在纸上画一画状态转移图标清楚每个状态的来源和去向。这个习惯帮我省下的调试时间比我写的任何代码都值钱。动态规划就是这样状态定义对了转移方程写对了整个题的难度就下降了一大半。