进入序列DP的世界：从玄学到有章可循
动态规划这门课，十个人学有九个人卡在“状态设计”这一步。刷了不少题，看了不少题解，感觉每个题解都是“显然可以设dp[i]为...”，轮到自己上手时，看到题目还是一脸茫然。这不是你不够聪明，而是入门方式没选对。动态规划算法家族里，序列DP（也叫线性DP）是最有套路可循的一类——它的处理对象是序列，状态是顺着序列下标一维铺开（偶尔二维），转移方向是从前往后线性推进。吃透序列DP，等于拿到了动态规划的半壁江山，后面再碰区间DP、树形DP、状压DP，都是在这个地基上垒砖。
这篇文章我打算用“一个状态就是一个故事”的视角，把序列DP的底层逻辑拆开讲：为什么它的思考顺序是“定义状态→写转移→定边界→找答案”，为什么经典模型里要那样设计dp数组的含义，以及二分优化、滚动数组这些进阶手法到底在优化什么。适合正在刷动态规划题单、备战算法竞赛或准备面试算法题的朋友，看完可以直接拿去做题验证。
序列DP的本质：顺着下标讲故事
1.1 序列给了我们一个“天然的决策顺序”
先想一个问题：为什么同样一道题，有的解法叫DP，有的解法叫贪心，有的解法叫搜索？核心区别在于——你有没有办法把大问题拆成结构相同的子问题，并且子问题的答案可以被反复使用。
序列DP的最大优势在于，序列本身就是从左到右排列的。比如一个长度为n的数组a[1], a[2], ..., a[n]，当我处理到下标i时，前面的下标1到i的状态已经全部计算完毕，后面的下标i+1到n还完全没有被影响。这在DP里叫无后效性。正因为存在这个天然的线性顺序，“从左往右扫一遍”的思想就能成为序列DP的骨架。
很多人学DP第一个接触的例子是爬楼梯：一次可以爬1阶或2阶，问爬到第n阶有多少种方法。设dp[i]是爬到第i阶的方法数，转移就是dp[i] = dp[i-1] + dp[i-2]。这个例子看似简单，其实已经包含了序列DP的全部要素——状态定义、转移方程、边界条件（dp[1]=1, dp[2]=2）、答案提取（dp[n]）。只是它太简单了，简单到让人感觉不到“状态设计”的存在。
1.2 状态设计：把“以i结尾”当成万能武器
序列DP里最常见的状态设计套路，是定义“以第i个元素作为某个结构末端的值”。为什么这个套路这么好用？因为序列DP问题的难点往往在于“两个元素之间能不能衔接”。如果我定义的是“前i个元素的最优值”，那我根本不知道这个最优值是哪个元素贡献的，也就不知道第i+1个元素能否接着往后拼接。但如果定义成“以第i个元素结尾的某个值”，那么第i+1个元素能否接上，只需要检查a[i+1]和a[i]之间的关系即可——转移条件一目了然。
用一个生活化的类比：你在规划一条旅行路线，如果你只记录“前n天玩了多少个景点”，那第n+1天要去哪里完全没法决策。但如果你记录的是“最后一天待在哪个城市、这趟行程看了多少景点”，那么第n+1天的行程就可以根据“最后一天的那个城市”来规划。这就是“以i结尾”状态设计的本质——它把“尾部信息”留在了状态里，让新元素能够清楚地知道能不能“接上去”。
1.3 无后效性与转移顺序的互相成就
顺着刚才的思路继续，序列DP的转移顺序通常就是下标从小到大的正序遍历，个别情况需要从大到小（比如0/1背包的滚动数组优化），但无论怎么变，核心原则是——当我们要计算dp[i]的时候，所有可能转移到它的dp[j]（j < i）都必须已经算好了。这是序列DP能用一个for循环跑完的根本保障。
我见过不少新手写序列DP翻车，就是因为有时候会写出“从i往前扫j”的代码，却忘了判断a[j]和a[i]的大小关系，或者漏掉了“当前元素不加入序列”的转移来源。这些问题归根到底还是状态故事没有讲完整。所以我一向建议写转移方程前，先用一句话把dp[i]的含义说清楚，再把“可能的来源”一一列出来。这个习惯能替你挡掉一半以上的bug。
三大经典模型拆解：LIS、LCS与编辑距离
2.1 最长上升子序列（LIS）：先朴素再二分
LIS问题描述很简单：给一个数组，求一个严格递增的子序列，使其长度最大。子序列不要求连续，只要下标递增即可。
我直接用“以i结尾”的思路走一遍：设dp[i]表示“以a[i]结尾的最长上升子序列长度”，那么任何下标j < i且a[j] < a[i]的dp[j]都可以作为dp[i]的前驱。于是转移方程：
- dp[i] = max(dp[j] + 1)，其中 j < i 且 a[j] < a[i]
- 边界条件：每个元素单独成序列时长度至少为1，所以dp[i]初始化为1
- 答案：max(dp[1...n])，而不是dp[n]
这里要特别强调一下最后一点——答案为什么是max而不是dp[n]？“以第n个元素结尾的最长上升子序列”，并不意味着这个子序列一定包含最后一个元素。如果严格递增的子序列在中间某个位置就已经达到最大长度，之后没有一个元素能接上去，那dp[n]完全可能不是最大值。这是序列DP初学者最容易踩的坑：以为dp[n]就是答案。
朴素实现的时间复杂度是O(n²)。当n达到10万甚至100万时，这个复杂度完全跑不动，于是就有了那个著名的二分优化：额外维护一个数组g，其中g[len]表示“长度为len的上升子序列所能达到的最小末尾值”。因为g数组天然是单调递增的，所以每次可以用二分查找（lower_bound）找到第一个大于等于a[i]的位置，更新g[pos]=a[i]，同时如果pos超出了当前最长的长度，就更新最长长度。
我强烈建议所有读者先手写一遍O(n²)的朴素版本，再去理解二分优化，否则很容易只记住了代码、没理解优化动机。
2.2 最长公共子序列（LCS）：二维状态表的经典走法
LCS处理的不再是一个序列，而是两个序列s1和s2。这时候一维的dp[i]就不够用了，状态要升到二维：设dp[i][j]表示“s1的前i个字符”与“s2的前j个字符”的最长公共子序列长度。
转移逻辑分两种情况：如果s1的第i个字符等于s2的第j个字符，那么这对字符可以并入公共子序列，所以dp[i][j] = dp[i-1][j-1] + 1；如果不相等，那么这对字符不能同时被匹配，答案只能在“忽略s1的第i个字符”或“忽略s2的第j个字符”中取较大值，也就是dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
边界条件是dp[0][]=0和dp[][0]=0，因为空串与任何字符串的公共子序列长度都是0。这个二维状态表是序列DP从一维走向二维的标志性起点，也是几乎所有字符串类DP问题的基础。
我在初学LCS的时候，曾经反复困惑一个问题：为什么字符相等时直接+1，而不是取max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1)这三个值的最大值？原因在于，当s1[i]==s2[j]时，dp[i-1][j-1]+1一定不小于其他两个候选。因为dp[i-1][j]最多是dp[i-1][j-1]+1（考虑s2[j]可能恰好是那个多出来的匹配），dp[i][j-1]同理。所以形式上虽然可以写成三者取max，但简化成“相等则左上+1，不等则左边上边取max”更干净，也更容易记忆。
2.3 编辑距离：三种操作的正向推导
编辑距离问题是在LCS基础上的下一个台阶：给定两个字符串s1和s2，允许对s1做插入、删除、替换三种操作，问最少多少次操作能把s1变成s2。
沿用LCS的二维状态框架：设dp[i][j]表示“s1前i个字符变成s2前j个字符”的最小编辑代价。转移来源有三种：
- 删除s1的第i个字符：dp[i][j] = dp[i-1][j] + 1，表示删掉一个字符后，前i-1个字符要变成s2前j个字符
- 插入一个字符到s1末尾（等价于从s2侧删除）：dp[i][j] = dp[i][j-1] + 1，表示s1前i个字符要变成s2前j-1个字符，再把s2的第j个字符作为新字符插入
- 替换s1的第i个字符，使它变成s2的第j个字符：如果s1[i]==s2[j]，代价是dp[i-1][j-1]；否则是dp[i-1][j-1] + 1
最终取三者最小值。边界条件是dp[0][j]=j（空串插入j次）和dp[i][0]=i（删除i次）。
从LCS到编辑距离，你会发现状态框架完全没变，变的只是转移方程里“允许的动作”不同——LCS只允许“匹配或忽略”，编辑距离则允许“删、增、替换”。这就是序列DP的妙处：模型是可以复用的，你只需要能在原模型的基础上做出正确修改。
优化手段与典型变式：压缩空间、改写状态
3.1 滚动数组优化：用两个一维数组代替二维表
LCS和编辑距离的二维DP表，如果直接用dp[n][m]存储，空间复杂度是O(nm)。当n和m都在5000以上时，1GB内存都未必够用。但仔细观察转移方程就会发现，dp[i][j]只依赖以下三个位置：
- 左上方向：dp[i-1][j-1]
- 上方：dp[i-1][j]
- 左侧：dp[i][j-1]
这意味着计算第i行时，只需要保留第i-1行的全部数据和当前行的滚动更新数据即可。因此把二维数组压缩成两个一维数组，也就是滚动数组优化。在LCS的代码实现中，通常用一个变量ld（左上角）记录dp[i-1][j-1]，因为当j从左往右更新时，这个值会被后面的更新覆盖，必须先存下来。
空间优化之后，复杂度变成O(nm)时间、O(m)空间。对于大多数竞赛和面试场景，这个优化基本够用。不过要注意，滚动数组虽然省内存，却丢失了回溯路径的能力——如果你想知道具体的公共子序列是什么，而不是只想知道长度，那就不能随便滚动，得保留完整DP表或者额外记录来源方向。
3.2 改写状态含义：LIS的二分优化的真正精髓
LIS二分优化很多人背过代码，但说不清楚为什么g数组是单调递增的。我换个角度解释：
朴素DP的O(n²)慢在哪里？慢在“找前驱”这一步需要遍历所有j < i。而二分优化做的事情是重新设计了一个状态g[len]——它记录了所有长度为len的上升子序列中，最小的末尾元素值。为什么这样设计是有用的？因为末尾元素越小，这个序列越“有前景”，越容易在后面接上更大的元素。
接下来需要证明g数组单调递增。反证法：如果存在len1 < len2但g[len1] >= g[len2]，那我们可以从长度为len2的、末尾为g[len2]的子序列里取出前len1个元素，它们的末尾必然不大于g[len2]（因为子序列是递增的，末尾是最小的），所以就能构造出一个长度为len1且末尾更小的子序列，这与g[len1]的最小定义矛盾。于是单调性成立。
有了单调性，每次对a[i]的处理就变成了：在g数组中二分查找第一个大于等于a[i]的位置，替换掉它。如果这个位置在边界之外，说明a[i]扩展出了新的更长序列。整个算法降为O(nlogn)。这个“改写状态含义来优化”的思想，在后面的很多DP优化里都是核心，值得好好体会，而不只是背模板。
3.3 常见变式：最大子段和与最长回文子序列
最大子段和问题虽然简单，却是序列DP思想的绝佳练习：给定数组，求连续子数组的最大和。设dp[i]表示“以a[i]结尾的最大子段和”，那么转移要么是a[i]单独成段，要么是接上dp[i-1]成为更大的段，即dp[i] = max(a[i], dp[i-1] + a[i])。答案是max(dp)。这个题的特点是连续，所以转移里不需要扫描前驱，这也是它比LIS简单的原因。
最长回文子序列则是另一个方向的变式：它在一个序列内部找对称结构，一眼看过去和线性扫描没关系。实际解法有两种：一种是把原序列倒过来求与原序列的LCS，另一种是用区间DP设dp[i][j]表示[i, j]区间内的最长回文子序列长度，按区间长度从小到大递推。后者已经跨入区间DP的范畴，但在序列DP阶段了解它的存在，对建立整体视野很有帮助——你会发现，当状态从“以i结尾”变成“区间(i, j)”时，转移方式和遍历顺序也会跟着改变。
实战场景：环形序列、带约束序列与数据结构辅助
4.1 环形序列破环成链
有些序列DP问题把序列首尾相连形成一个环。最经典的例子如“环形数组的最大子段和”——普通线性数组的解法可以直接套用，但环的存在让答案可能横跨首尾。处理手法基本是固定套路：把环剪开，复制一遍数组，让长度为n的环变成长度为2n的线性数组，然后在线性数组上跑DP，限制子数组长度不超过n。通过枚举起点的方式，可以把所有跨越首尾的段都覆盖到。
这种做法的时间复杂度通常是O(n²)起步，因为要枚举起点（对于某些问题是O(n)）。如果你在洛谷的动态规划题单里碰到环形DP标记的题目（比如“环形石子合并”），注意它往往不是纯序列DP，而是“枚举断点 + 区间DP”的组合。这提示我们一个重要的模型认知：序列DP和区间DP之间没有壁垒，根据状态描述中是否出现“区间”，灵活切换。
4.2 带约束的序列DP：恰好选K个
做题时经常遇到“恰好选K个物品使总值最大”的变式，典型如最长递增子序列的长度必须恰好等于K，或者选择K段互不重叠的子数组使总和最大。这种带数量约束的序列DP，处理方法是给状态数组增加一维：设dp[i][k]表示“处理完前i个位置，已经选出k个结构的最小/最大值”。
以“选择K个不相交子段使总和最大”为例（经典题目：有N个整数，选K个子段求最大总和），设dp[i][k]表示考虑前i个元素、已经选了k个子段的最大总和，并且强制第i个元素属于第k个子段。转移有两种来源：
- 第i个元素单独成为第k个子段的开头：dp[i][k] = max(dp[j][k-1]) + a[i]，其中j < i
- 第i个元素接续在第k个子段末尾之后：dp[i][k] = dp[i-1][k] + a[i]
这个转移里的第一个来源需要前缀最大值优化，否则复杂度会变成O(n²k)。此时你会惊喜地发现，之前用的“前缀max”思想又回来了——为了快速求max(dp[j][k-1])，我们可以维护一个best数组，随i递增同步更新。这类优化在竞赛题中叫“斜率优化/前缀最值优化”的雏形，序列DP阶段掌握这个就足够了。
4.3 数据结构辅助：树状数组与线段树加速转移
当LIS问题遇到“a[j] < a[i]”和“j < i”双重条件时，除了二分优化，还可以用树状数组（Fenwick树）或线段树维护“以值域为下标、DP值为权值”的前缀最大值。具体操作是：按i从小到大遍历，对每个a[i]，用树状数组查询值域上小于a[i]的所有dp值中的最大值，加1后更新到a[i]对应的值域位置上。
这种做法的本质是把“线性扫描前驱”替换成“值域上的区间查询”，时间复杂度O(nlogV)（V是值域范围）。它比二分优化更通用——当转移条件从“小于”变成“大于等于”或“不等于”时，二分优化往往难以套用，但值域数据结构却可以灵活修改查询条件。如果你在刷题时遇到带权值的LIS变式，可以优先尝试这个思路。唯一的代价是代码量上来了，需要手写树状数组模板，并且要对值域做离散化处理。
从题目到代码的完整推导流程
5.1 一望二定义三转移四边界五答案
处理任何一道序列DP题，我都推荐按下面的顺序走一遍，并且写在草稿纸上，不要直接上手敲代码：
- 看题：确定输入是序列，输出是最值（长度、和、代价等），大概率要DP
- 定义状态：用一句话说清楚dp[i]（或dp[i][j]）代表什么。是“以i结尾”还是“处理完前i个”，必须想清楚
- 写转移方程：列出所有可能转移到当前状态的前驱，并用语言解释每个转移对应什么动作（选上/不选/跳过/拼接/替换）
- 定边界：dp数组该初始化成什么？0、1、负数无穷大还是正无穷大？
- 找答案：答案究竟是dp[n]、max(dp数组)、还是dp数组里的某个特定下标？
前四步是几乎所有题解都会写的，第五步却经常被忽略——但实际做题里第五步最致命，因为边界条件和答案位置错误往往不会导致编译报错，而是导致样例全过、提交全挂。
5.2 三道有代表性的练习题路线
如果你想把序列DP彻底吃透，我建议按如下顺序刷题，每道题都要自己先把状态设计写在纸上再动代码：
- 第一道：LIS朴素版 + 二分优化版（自己手写两遍）。这道题检验你是否真正理解“以i结尾”
- 第二道：编辑距离。这道题检验你是否能在二维状态表上理清三种操作的转移关系
- 第三道：带约束的序列DP，比如“K个不相交子段最大和”。这道题检验你是否能增加维度处理数量约束，并想到用前缀max做优化
如果你喜欢用题单刷题，洛谷的动态规划题单是目前覆盖面最全的，里面按难度把线性DP、区间DP、树形DP都做了分级，非常适合按序推进。我的习惯是每做完一道题，就把它的状态定义、转移方程和踩坑点记在模板笔记里，刷到后面你会发现不同题的模板笔记在互相交叉引用——这正是序列DP套路化的证据。
5.3 从“背模板”到“理解模型”的关键一步
最后说点心态层面的东西。序列DP的题目做了几十道之后，很容易产生一种“所有题都是套路”的错觉，于是做题变成套模板。但一旦遇到一个需要你打破模板的题（比如状态不是以i结尾而是以某种奇偶性为状态），就会彻底翻车。
我的建议是，每次刷完一道题，都问自己三个问题：状态定义还能不能换个说法？转移方程是怎么想到的？如果数据范围扩大十倍，哪里会最先撑不住？这个过程比多刷十道题都更值钱，因为它逼着你去理解模型本身，而不是记住题解的模样。
序列DP之后的路
真正在实战里把序列DP用到极致的人，通常已经不只是会做这几道经典题目，而是把序列DP当作一种“思考前置步骤”——说话之前先问自己：这里有没有一个顺序？能不能定义状态？能不能写出转移？一旦这种思维成为习惯，后面碰到的字符串匹配、概率DP、博弈论DP都不会太陌生。
在我个人的刷题经历里，最深的体会是：序列DP学到最后，记住的不是LIS、LCS的代码，而是那种“顺着下标讲故事、每一步都知道自己在哪、也知道下一步能走到哪”的感觉。这种感觉会在你做所有算法题的时候反复出现。如果你现在正卡在状态设计上，别急，拿起一道最简单的题，写满一整张草稿纸的转移解释，再回过头看，你会发现原来“玄学”其实是有章法的。
