很多刚开始接触动态规划的人一看到“状态转移方程”这五个字就头皮发麻。题解铺天盖地每一篇都说“不难”轮到自己上手就是写不出来。我见过不少学算法的朋友包括带过的一些选手卡在DP入门这个坎上大半个月。如果你也有同样的感觉我的建议是一句话先把线性DP经典题目吃透别的先不碰。线性DP是动态规划里最基础、最透明、也最适合建立思维方式的一类问题。它的状态和转移都长在一条线上你能清清楚楚看见“前一步是怎么推向下一步”的。这一篇不整虚的把我反复验证过的经典题、状态定义、代码实现和容易踩的坑全部列出来希望能帮你跨过这道坎。1. 线性DP到底在解决什么问题1.1 什么才叫“线性”说个最直白的理解。动态规划的本质是把一个大问题拆成一步步的小问题用“状态”记录每一步的答案。所谓线性DP就是这些小问题按照一个顺序排下来像一条链子一样后面的状态只依赖前面若干个状态不会突然跳到很远的地方去。举个生活化的例子。你去排队买奶茶队伍里每个人只要看一眼前面那个人买到什么就知道自己下一步该做什么。谁都不需要回头去看队伍最后面发生了什么。线性DP就是这个逻辑dp[i]表示处理到第i个位置时的答案转移的时候只从dp[i-1]、dp[i-2]这些相邻位置拿信息。注意这里的“线性”不是指题目数据一定是一维数组。两个序列的匹配问题比如最长公共子序列状态是二维的但它的推进方向也是线性的——逐个字符往后扫每走一步只和前一步的状态有关。所以线性DP的范围其实很广凡是在序列、字符串、路径上按顺序递推的都可以归到这个大类里。1.2 为什么入门必须先啃线性DP很多人学DP动作太快上来就看区间DP、树形DP、状压DP结果就是看一个崩一个。原因很简单这些复杂DP的类型里也都蕴含着线性推进的影子但额外叠加了区间合并、树上遍历、位运算这些负担。如果连最基础的“状态怎么定义、转移方程怎么写、边界条件怎么设”都没形成肌肉记忆叠加任何复杂度都会直接崩盘。线性DP的最大价值就是你能在最干净的环境里练好这三板斧。以我自己的经验把这十几道经典题目吃透之后再去看区间DP会突然觉得“这不就是在线段上做线性递推嘛”看树形DP也会发现无非是“DFS序之后做后序处理”。所以线性DP不是终点但它一定是最值得投入的第一站。2. 经典题目拆解与状态设计思路2.1 爬楼梯与斐波那契先分清递推和DP很多教程把斐波那契数列当作DP第一题但严格说它只是一个递推。不过作为心智模型的起点它确实最自然。台阶问题稍微包装了一下每次可以上1级或2级台阶问爬到第n级有多少种不同的走法。状态定义非常直接dp[i]表示爬到第i级台阶的走法数。要想到达第i级最后一步要么从i-1跨1级上来要么从i-2跨2级上来。所以转移方程是dp[i] dp[i-1] dp[i-2]边界条件可以有两种写法。习惯上设dp[1] 1dp[2] 2然后从i 3开始递推。另一种更统一的做法是设dp[0] 1dp[1] 1从i 2开始推。我第一次自己写的时候就栽在dp[2]上后面想通了一个验证技巧永远拿最小规模的输入去手算一遍。比如n 2时答案显然是2如果你的初始化算出别的数那就是边界错了。这道题虽然简单但一定要亲手写一遍空间优化版本。因为dp[i]只用到dp[i-1]和dp[i-2]根本不需要开一个长度为n的数组用两个变量滚动就够了。这个“滚动数组”的思想在后面的数字三角形、LCS里都还会用到。2.2 最大子段和搞懂“以 i 结尾”的精髓题目给定一个整数数组求一个连续子数组使得它的和最大。这个题看起来和爬楼梯长得很不一样但它教会我们一个非常重要的状态设计技巧——用“以某个位置结尾”来定义状态。先说错误示范。很多人第一反应是设dp[i]表示“前i个元素中的最大子段和”。这种定义下想知道dp[i]怎么从dp[i-1]转移过来就得知道之前那个最优子段到底有没有覆盖到i-1。如果覆盖到了那a[i]可以接上去如果没覆盖到接上去就破坏了“连续”的定义。你会发现这个状态根本没法写出简洁的转移方程。正解是设dp[i]表示“以第i个元素结尾的最大子段和”。这样一来要不要把a[i]和前面的子段拼在一起只需要看dp[i-1]是否划算dp[i] max(a[i], dp[i-1] a[i])如果dp[i-1]是负数那不如从a[i]重新开始否则就接上去。最终的答案是所有dp[i]的最大值而不是dp[n]。这个细节很多人第一次会漏掉因为最优子段不一定包含最后一个元素。每个i只依赖i-1所以连滚动数组都不用直接用一个变量记录上一轮的结果空间复杂度降到 O(1)。这就是常见的 Kadane 算法。2.3 最长递增子序列从 O(n^2) 到 O(n log n)最长递增子序列LIS是线性DP里承上启下的一道题因为它同时训练了朴素DP和贪心二分两种思路。朴素做法的状态定义很有代表性dp[i]表示“以第i个元素结尾的最长递增子序列长度”。注意又是“以 i 结尾”。转移时就往前找所有j i且a[j] a[i]严格递增的位置尝试把a[i]接到以j结尾的序列后面dp[i] max(dp[j] 1) 其中 j i 且 a[j] a[i]每个i都要扫描一遍前面的所有j复杂度是 O(n^2)。单串长度到5000以内还能顶一顶到10^5就直接超时了。O(n log n) 的做法是一个贪心思维维护一个数组dd[k]表示长度为k1的递增子序列中末尾元素的最小值。核心思想是对于同样长度的子序列末尾元素越小以后越容易继续接长。遍历每个a[i]在d里找到第一个大于等于a[i]的位置把它替换掉如果不存在说明可以接在更长序列后面直接追加。这里一定要用二分查找否则优化就白做了。要注意一点如果题目要求的是非严格递增也就是允许相等那把lower_bound换成upper_bound即可。这两个函数的区别我在实战群里已经看到无数人踩过了。2.4 最长公共子序列二维状态表的构建LCS 的状态定义和前面不太一样因为它有两个字符串。设dp[i][j]表示“字符串 A 的前i个字符”和“字符串 B 的前j个字符”的最长公共子序列长度。转移时分两种情况。如果A[i-1] B[j-1]说明最后一个字符可以匹配上那就在前i-1和前j-1的结果基础上加1否则只能分别从A丢掉最后一个字符、或从B丢掉最后一个字符取两者中的较大值if (A[i-1] B[j-1]) dp[i][j] dp[i-1][j-1] 1; else dp[i][j] max(dp[i-1][j], dp[i][j-1]);很多新手会在这里纠结两个字符不相等时为什么直接取 max 而不做其他处理因为公共子序列不要求连续丢掉其中一个字符串的尾部字符完全不影响前面部分的最优性。正是“子序列不连续”这个性质让这个转移成立。写代码时最容易犯的错是下标越界。A 和 B 的索引从0开始但 dp 的维度从1开始更舒服这样dp[0][j]和dp[i][0]都表示“其中一个字符串为空”值天然为0不需要额外初始化。我在自己练习时喜欢用从1开始的dp数组配合A[i-1]去访问原串保证逻辑和代码对齐。LCS 的空间也可以优化成两行滚动但要注意它依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]三个位置滚动时需要用一个临时变量保存左上角的值否则会被覆盖掉。2.5 数字三角形路径类DP的模板数字三角形是几乎每个算法教程都会收录的题目因为它是“从起点到某个位置的路径最优化”这类问题的标准模板。题目描述是给一个三角形的数组从顶部出发每次可以走到下一层相邻的两个位置之一求从顶到底经过的数字之和的最大值。状态设计有两种方向。一种是自顶向下dp[i][j]表示从顶部走到第i行第j列的最大路径和它可以从左上和右上两个父节点转移过来。另一种是自底向上dp[i][j]表示从(i, j)出发走到最底部的最大路径和它从下一层的两个子节点转移过来。我个人更推荐自底向上因为边界更好处理最终答案就是dp[0][0]不需要在最后一行里再扫一遍求最大值。dp[i][j] a[i][j] max(dp[i1][j], dp[i1][j1])这个题的空间优化很有代表性可以只开两行滚动甚至如果数据允许直接在原数组上从下往上做覆盖也不会出错。因为更新a[i][j]时依赖的是a[i1][j]和a[i1][j1]这两行已经处理过了且当前行往上不会再被用到。这种“原地滚动”的思路在竞赛代码里非常好看。3. 从题到代码完整实操与关键细节3.1 四步走状态定义、转移方程、初始条件、答案位置我总结了一个固定的实操流程带过的新手只要严格按这个顺序走很少会卡到写不出代码的地步。第一步写清楚状态定义。不要让自己的状态是一个含糊的“前 i 个元素的最优值”一定要明确后缀词到底是以第i个元素结尾还是处理完前i个元素以后的结果。这两者一字之差转移方程就完全不一样。第二步写出转移方程。这一步建议先在草稿纸上画一个小数据人肉模拟一遍整个过程。比如最大子段和拿[-2, 1, -3, 4]这个例子手推很快就能发现“以 i 结尾”的正确性和“前 i 个元素”定义下的别扭。第三步确定初始条件。dp[0]是0还是1dp[1]要不要单独给值数组从0开始还是从1开始这些必须统一。最好的验证方式是拿最小的合法输入比如n1或空数组手动运行一遍。第四步确认答案从哪里取。有的答案是dp[n]比如爬楼梯有的是所有dp[i]的最大值比如最大子段和、LIS有的就是dp[0][0]比如自底向上的数字三角形。答案位置选错最坑因为程序完全不会报错输出却怎么都不对。3.2 空间优化的两种常见套路第一种滚动数组适合状态只依赖前一层或前两层的情况。爬楼梯用两个变量数字三角形用两行一维数组LCS用两行二维数组。滚动数组不会改变时间复杂度但它把空间从 O(n) 甚至 O(nm) 降到了 O(1) 或 O(min(n,m))这在内存受限的题目里是救命级别的优化。第二种原地震动适合依赖方向明确且依赖层已经被处理过的情况。数字三角形自底向上就可以直接改原数组这是最省事的写法。这里必须提醒一个非常容易翻车的点不是所有DP都能随便压缩成一维。背包问题里为什么要从大到小枚举容量因为一维数组会共享数据如果不逆序一个物品可能被选进结果多次变成了完全背包。判断能不能压缩的核心只有一个——看压缩后会不会覆盖掉转移还需要用到的值。3.3 时间复杂度估算什么时候用朴素、什么时候必须优化我把上面几道经典题的时间与空间复杂度整理成一个表方便对号入座。题目状态维度时间复杂度空间复杂度朴素备注爬楼梯一维O(n)O(n)可滚动到 O(1)最大子段和一维O(n)O(n)本质是 Kadane可 O(1)最长递增子序列一维O(n^2)O(n)贪心二分可 O(n log n)最长公共子序列二维O(nm)O(nm)可滚动到两行 O(min(n,m))数字三角形二维O(n^2)O(n^2)可原地修改到 O(1) 或两行滚动做题时先看数据范围。如果n只有1000O(n^2) 完全没问题如果n到10^5那基本上就得想 O(n log n) 甚至 O(n) 的做法。很多算法竞赛的误区不是不会优化而是不需要优化时过度优化浪费了思考其他细节的时间。4. 常见问题与排查技巧实录4.1 边界条件反复出错边界条件是最让人头大的地方因为每道题都不一样。爬楼梯的dp[0]到底设成1还是0很多人会记混。我的办法不是背结论而是拿小数据验n1答案应该是1所以dp[1]1n2答案应该是2所以dp[2]2或者dp[0]1, dp[1]1用两个最小用例同时校验一旦初始化有问题立刻会被发现。这比空想一百遍都管用。LCS 的边界相对友好空串对应的行和列天然是0。但要注意如果题目的字符串下标从0开始传入而 dp 数组又喜欢从1开始写转移时访问原串必须统一减一。这种“数组开头错位”的问题往往在i1或j1时第一个字符匹配不上排查时看到错位的规律就明白了。4.2 状态定义模糊导致转移写不出来我见过很多人在草稿纸上画了半天最后卡在原地原因几乎都是状态定义不清。举一个高频问题打家劫舍要求不能偷相邻的两家问最多偷多少。有人想定义dp[i]为“偷到第 i 家时的最大金额”。然后发现写转移时要区分第i-1家到底偷没偷否则不知道第i家能不能偷。这个问题的根源是状态里少了一个标记位。更好的定义是dp[i]表示“从前 i 家中能获得的最大金额”。这样第i家有两种决策不偷继承dp[i-1]偷就必须保证第i-1家没偷所以是dp[i-2] a[i]。dp[i] max(dp[i-1], dp[i-2] a[i])这个例子很好地说明了一个判断标准写转移时如果觉得需要用额外的信息才能确定下一步怎么走那八成是状态定义少了一维或者选错了角度。4.3 一维化后覆盖顺序出错把二维DP压缩成一维或两行是把双刃剑。数字三角形倒着扫是安全的因为更新当前行不会影响后续依赖但如果你对顺序没把握就把两行数组画出来用一支笔模拟三四个元素的更新过程。我之前遇到过一个非常典型的错误对 LCS 做滚动数组优化时直接开两行dp[2][n]但忘了保存dp[i-1][j-1]的值。因为更新dp[i][j]需要左上角的值而在同一轮滚动中dp[i-1][j-1]其实已经被上一行覆盖了。正确的做法是在内层循环里先保存一个pre变量记录上一次的“左上角”然后逐行更新。写滚动优化时先画一个3乘3的表模拟比对着代码硬想要快得多。4.4 手算小样例代替一切无头绪 Debug程序跑出来结果不对别急着加输出、断点满天飞。先自己手算一个非常小的例子把 dp 表完整填出来再拿程序输出对比。整个过程通常不超过两分钟却能精准定位问题出在第几层循环、哪一次转移写错了。排查顺序我建议固定成先看初始条件再看转移方程最后看答案到底取的哪个位置。按这个顺序查我几乎没有遇到过查不出来的线性DP问题。如果你确定转移和边界都对但答案依然错那就去看下标——我在实际带人的过程中发现十有八九是原串下标和 dp 下标的偏移量没对齐。5. 从会做题到举一反三5.1 给经典题加上限制条件就变成新题线性DP最有趣的地方在于加一个限制、改一个转移就能演化出一大堆看起来完全不同、实则同源的问题。打家劫舍就是最大子段和的“不能相邻”版本。股票买卖问题则是另一个经典例子dp[i][0/1]表示第i天结束后手里是否持有股票的最大收益多了一个维度来记录“是否持股”这个状态。你会发现只要熟练掌握了基础线性DP的状态设计这些变形就是水到渠成的思路扩展。我自己常用的一个方法是拿到新题后先不要看它是什么类型先问三个问题状态沿着什么顺序推进每一步有哪些决策每个决策对状态的影响是什么这三个问题回答清楚了线性DP的大体框架就浮出来了。5.2 如何识别“这道题是线性DP”从题目特征上看只要出现了“序列”“数组”“字符串”“沿时间线决策”这些关键词而且问题能用递推关系描述优先往线性DP上想。路径类题目如果每一步只能走到相邻位置也是线性DP的经典场景。识别题型的另一个信号是看状态之间是否存在明显的“阶段”关系。比如一个任务安排问题工作项按时间排序每个任务做或不做都会影响后续决策这种就是非常标准的线性DP。把“阶段推进”的意识建立了你就不容易被伪装成背包或贪心的题目带偏。5.3 训练优先级与进阶路线我给新手的推荐顺序是爬楼梯最大子段和数字三角形打家劫舍LISLCS最后再来一道综合性的“编辑距离”收尾。前三个是热身中间的题目让你掌握“以 i 结尾”和“加维度”两种状态设计范式最后的编辑距离则是把二维DP和分类讨论练到融会贯通。每一道题至少亲手写两遍第一遍写完对照题解优化第二遍合上题解复现。第二遍的作用是检验你到底理解了还是纯靠记忆抄了一遍。很多人在“好像懂了”这个舒适圈里呆太久到了真正上场比赛才发现写不出转移方程。别问我怎么知道的问就是当年我也这样。我自己刷DP最大的体会是状态定义就是整个题的灵魂。定义对了转移方程顺水推舟定义错了后面的工作全是白费。如果你现在正卡在不知道怎么写状态试着把所有候选状态定义都写在纸上然后逐一模拟小样例哪个定义能写出清晰、无歧义的转移就用哪个。这个笨办法在绝大多数线性DP题目上都很管用。