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到阶段i+1，哪个量变了？哪个量不变？改变了的是状态里的哪一项？如果这个量不在状态里，转移方程就写不出来。比如车辆问题中，如果状态只记录“当前站点编号”，却没有记录“剩余装载量”，那么到下一站能否装货就无法判断。这就是我反复强调状态三要素的原因——每一项都有它的物理意义和存在必要性。

有了这个视角，你会发现线性DP其实是一种“建模方法论”而不是模板。它教你的是：把过程拆成有序阶段、定义每阶段的完整快照、找出相邻阶段状态的关系。这套方法论学会了，洛谷题单里的各种变体题、工程里的调度问题、甚至一些看似和DP无关的最优化问题，你都能一眼看穿它的递推结构。

2. 洛谷经典题单实战拆解：从推导到AC

2.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结尾，才能保证下一项i+1接上时区间仍然连续。这就是线性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)就已经是千万级的运算量。实际的车辆调度里，站点数量可能更大，这时候就需要针对具体场景做状态压缩。我在工程里最常用的是滚动数组：

vector<int> 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个站点，每个站点的货物重量与价值如下表：

用滚动数组模拟一遍。初始dp[0] = 0，其余为负无穷（表示不可达）。处理站点1（重量3，价值4，倒序遍历）：dp[3]从不可达变成4，此时dp数组在重量3的位置有值。处理站点2（重量4，价值5）：dp[4]=5，dp[7]=max(dp[7], dp[3]+5)=4+5=9。处理站点3（重量5，价值6）：dp[5]=6，dp[8]=dp[3]+6=10，dp[9]=dp[4]+6=11。处理站点4（重量2，价值3）：dp[2]=3，dp[5]=max(6, dp[3]+3=7)=7，dp[6]=dp[4]+3=8。处理站点5（重量1，价值1）：dp[1]=1，dp[3]=4，dp[4]=max(5, dp[3]+1=5)=5，dp[6]=max(8, dp[5]+1=8)=8。

最终答案是dp[10]或所有dp[w]中的最大值。手动模拟一遍就会发现，滚动数组的倒序遍历到底在保护什么——它保证了每个站点只被考虑一次。如果你正序遍历，站点1的货物会被反复装进背包，得出一个远超实际价值上限的答案。模拟完这个过程，我认为你对“为什么倒序”这个问题就不会再有疑惑了。

4. 调试技巧与常见错误实录

4.1 边界与初始化的坑

动态规划题目的WA，十有八九出在初始化和边界上。我举一个常见的例子：LIS问题中，如果你把dp数组初始化为0，而序列第一个元素是负数，那么dp[1]会保持0，后续所有转移都从这个错误起点出发，答案就偏小。正确的初始化是dp[i] = 1（每个元素至少可以独自构成长度为1的子序列），然后从i=1开始递推。这个“1”就是最小子问题的正确答案——只有它对了，递推链才会对。

另一个边界问题是下标越界。在二维DP中，dp[i-1][j-1]在i=1或j=1时会访问到下标0——这通常是合法的，只要你的数组从0开始分配且dp[0][]和dp[][0]被正确初始化为0。但如果数组开小了，或者在转移前忘记判断j-1是否合法，就越界访问，轻则答案错误，重则运行时崩溃。我的习惯是数组一律开成MAXN+5，且全局变量默认清零，这样边界处理会宽松很多。

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数组的有效长度。

vector<int> 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。不过说实话，斜率优化对数学推导能力要求比较高，我建议先把前面的所有优化都弄熟练了，再啃这一块。

最后再分享一个小技巧：不管是刷洛谷动态规划题单，还是做工程里的车辆调度问题，拿到题先别急着写代码，花两分钟在纸上画一画状态转移图，标清楚每个状态的来源和去向。这个习惯帮我省下的调试时间，比我写的任何代码都值钱。动态规划就是这样，状态定义对了，转移方程写对了，整个题的难度就下降了一大半。