刷题几年我逐渐发现一个现象动态规划里最常见的基础模型——LIS、LCS、LCIS很多人会单独遇到但很少真正把它们放在一起比较。最长递增子序列Longest Increasing Subsequence、最长公共子序列Longest Common Subsequence、最长公共递增子序列Longest Common Increasing Subsequence名字像状态设计有血缘关系优化思路却各不相同。这篇文章我打算把这三个序列问题模型一网打尽从最朴素的DP讲到O(nlogn)的优化从空间压缩讲到路径还原顺手把容易踩的坑整理成速查清单。适合正在啃动态规划的新手也适合拿来当竞赛复习笔记的老手。1. 三个问题模型先看懂它们到底在问什么1.1 用大白话重新定义三个问题先别急着看公式。我用自己的话把这三个问题讲清楚保证不绕弯。LIS最长递增子序列给你一串数允许跳着选选出来的数必须按原来的顺序并且严格递增问最多能选几个。比如数组 [1, 9, 2, 8, 3, 7]答案是 3可以选 [1, 2, 3] 或 [1, 2, 7]注意子序列不需要在原始数组里连续这是它跟子数组最大的区别。LCS最长公共子序列给你两个序列各自跳着选选出两个都有的、顺序一致的公共子序列问最长多少。比如 abcde 和 ace公共子序列是 ace长度 3。这个模型最常见的现实场景是文本 diff 和基因序列比对本质都是找两份数据之间最相似的那部分骨架。LCIS最长公共递增子序列它是前两个的叠加态。两个序列都要满足而且选出来的公共子序列还必须严格递增。比如 a [1, 2, 3, 4]b [2, 3, 4, 1]公共递增子序列是 [2, 3, 4]长度 3。LCIS 不能只靠 LIS 或者只靠 LCS 解决它需要同时兼顾公共和递增两个约束。1.2 三个问题背后的共同骨架把三个问题并排看你会发现它们共享同一套底层逻辑。第一依赖的扫描单位都是子序列不是子数组所以状态设计里不会出现必须连续这类限制。第二它们都在求最值长度这天然适合动态规划的最优子结构。第三也是最重要的一点三个问题的状态转移里都有以某个元素结尾的意识。LIS 明确以 a[i] 结尾LCIS 明确以 b[j] 结尾LCS 虽然用的是前 i 个、前 j 个前缀型状态但在路径还原时本质还是靠最后一个匹配的字符来回溯。第四它们的优化路径有相似的逻辑朴素 DP 是 O(n²) 或 O(nm)优化方向要么是用单调性做二分要么是压缩无用状态。所以我把它们放在一篇里讲因为学完一个模型的状态设计为什么这么定另外两个真的很好推。2. LIS从 O(n²) 到 O(nlogn)我为什么推荐先写朴素 DP2.1 O(n²) 朴素 DP搞懂状态设计的根源LIS 的状态定义是面试里最容易讲不清楚的一个。我见过的错解多半是把 dp[i] 定义成前 i 个数的最长递增子序列长度这样定义很直觉但转移时会发现前 i 个数的 LIS 长度和最后一个数的值没有绑定关系你无法判断新的数 a[i] 能不能接上去。所以正确做法是dp[i] 表示以 a[i] 结尾的最长递增子序列长度。为什么要强制以 a[i] 结尾因为递增子序列的结尾元素决定了未来还能不能继续往后接。结尾元素越小越有机会接更长的序列结尾元素越大就越难接。这个结尾值就是整个状态转移的灵魂。这样转移就非常自然。初始化所有 dp[i] 1因为单个元素本身就是一个长度为 1 的递增子序列。然后用两重循环对于每个 i遍历所有 j i如果 a[j] a[i]说明 a[i] 可以接在以 a[j] 结尾的序列后面于是 dp[i] max(dp[i], dp[j] 1)。int lis_n2(const vectorint a) { int n a.size(), ans 0; vectorint dp(n, 1); for (int i 0; i n; i) { for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }这个版本我建议每个人都亲手写一遍。因为它把动态规划最核心的东西暴露得很彻底状态存什么、转移找什么、答案在哪里。写熟了后面优化才不慌。2.2 O(nlogn) 贪心二分替换为什么是对的当 n 到 10^5 级别O(n²) 直接超时这时候需要上贪心二分。核心思路一句话维护数组 dd[len] 表示长度为 len 的递增子序列里可能的最小末尾值。注意这里是最小末尾值不是末尾值最小的那个子序列。长度为 2 的递增子序列可能有多种结尾比如 3 和 7保存 3 一定比保存 7 好因为 3 更小、后面更容易接新元素。这个贪心是正确的因为我们要的是最大长度只要长度不变、末尾更小就不会丢失任何可能更优的后续扩展。具体流程d 数组初始为空从左到右扫描 a。对每个 a[i]在 d 里找到第一个大于等于 a[i] 的位置 lower_bound如果存在就把那个位置替换成 a[i]如果不存在说明 a[i] 比所有已知的最小末尾都大可以直接扩展出一个新长度d.push_back(a[i])。int lis_nlogn(const vectorint a) { vectorint d; for (int x : a) { auto it lower_bound(d.begin(), d.end(), x); if (it d.end()) { d.push_back(x); } else { *it x; } } return d.size(); }很多人第一次看这个代码会问直接替换不会破坏 d 数组的单调性吗不会。d 始终保持严格递增因为 lower_bound 找到的是第一个不小于 x 的位置这个位置替换后仍然不小于前一个元素否则 lower_bound 不会停在那里同时必然小于后一个元素因为后一个元素原来就比这个位置的值大现在这个位置变小了只会更小所以 d 的单调性保持完好。这是整个二分优化正确性的基础。这里要特别注意一个坑d 数组里的东西不是最长递增子序列本身它只是用来求长度的辅助数组。如果你直接拿 d 当答案输出很可能得到一组跟原序列顺序对不上的数。我刚开始学的时候就被这个坑坑过后面路径还原部分会专门讲。2.3 LIS 路径还原记录插入位置倒序收集竞赛题里经常要求输出最长递增子序列这时候光知道长度不够得把真正的序列还原出来。做法是在二分插入的同时记录每个 a[i] 最终在 d 数组里落入的位置 idx[i]从 1 开始计数。等所有元素处理完d.size() 就是最长长度 len。然后从数组末尾往前扫找到第一个 idx len 的元素它一定是最终答案序列的最后一个元素。接着找 idx len - 1 的倒着收集最后反转。vectorint lis_with_path(const vectorint a) { vectorint d, idx(a.size()); for (int i 0; i (int)a.size(); i) { auto it lower_bound(d.begin(), d.end(), a[i]); int pos it - d.begin(); // pos from 0 if (it d.end()) d.push_back(a[i]); else *it a[i]; idx[i] pos 1; // 记录 1-based 位置 } int len d.size(); vectorint ans; for (int i (int)a.size() - 1; i 0 len 0; i--) { if (idx[i] len) { ans.push_back(a[i]); len--; } } reverse(ans.begin(), ans.end()); return ans; }为什么要倒序收集而不是正序因为 idx[i] 记录的是扫描到 i 时刻它在 d 中的位置这个位置是动态变化的。某个 idx len 的元素在后续扫描中可能被替换掉如果我们正着扫可能会把后来被替换的元素误当成最终序列的一部分。从后往前扫能保证每个被选中的元素在最终阶段仍然有效。这个细节我自己写错过好多次后来形成习惯只要涉及路径还原一律先记录插入下标再倒序回溯。2.4 LIS 变体不下降、递减、二维偏序严格递增用 lower_bound 找第一个大于等于 x 的位置替换这是为了避免相等元素重复使用。如果题目要求最长不下降子序列允许相等那么二分查找要换成 upper_bound找第一个大于 x 的位置。因为相等元素可以排在后面所以不必替换掉等于自己的值。选错 lower_bound 和 upper_bound答案会差很多尤其是数组里大量相同元素的时候这个细节务必记牢。最长递减子序列就简单了把原数组每个数取反或翻转比较方向再跑 LIS 模板就行。LIS 最大的应用场景其实是二维偏序问题。比如给一堆点 (x, y)找出最长的点列使得 x 递增且 y 递增。常规做法是先按 x 排序x 相等时按 y 降序排序然后对 y 做 LIS。x 相等时按 y 降序是精髓可以防止在同一个 x 下选取多个点因为按 y 递减排LIS 在相同 x 内只能取一个 y。这类题在算法竞赛里非常常见LIS 的递增天然承接偏序关系。3. LCS二维DP的教科书级模板以及空间压缩3.1 状态定义为什么用前缀而不是以谁结尾LCS 跟 LIS 最大的不同是它有两个序列匹配的最后一对字符不一定是 a[i] 和 b[j] 同时相等可能是 a 的前 i-1 个和 b 的前 j 个已经匹配完了最后一个字符来自 b[j]也可能是反过来。所以不能简单定义以 a[i] 结尾因为两个序列的尾部不一定会对齐。标准定义是dp[i][j] 表示 a 的前 i 个字符和 b 的前 j 个字符的最长公共子序列长度。转移分两种情况a[i] b[j]当前这一对可以同时匹配dp[i][j] dp[i-1][j-1] 1a[i] ! b[j]当前这一对没法同时匹配只能丢掉其中一个dp[i][j] max(dp[i-1][j], dp[i][j-1])第一眼看上去这个转移像一个选或不选的决策。a[i] 和 b[j] 相等时把它们配对明显不亏因为不影响前面的匹配不相等时要么跳过 a[i]要么跳过 b[j]取两者中更长的。边界条件 dp[0][j] 0 和 dp[i][0] 0因为空序列和任何序列的公共子序列长度都是 0。举个小例子。a [1, 9, 2]b [1, 2]。手动推一遍dp[0][] 0dp[][0] 0i1, a[1]1j1 时相等dp[1][1]dp[0][0]11j2 时不等dp[1][2]max(dp[0][2], dp[1][1])1i2, a[2]9j1 时不等dp[2][1]max(dp[1][1], dp[2][0])1j2 时不等dp[2][2]max(dp[1][2], dp[2][1])1i3, a[3]2j1 时不等dp[3][1]max(dp[2][1], dp[3][0])1j2 时相等dp[3][2]dp[2][1]12最终 dp[3][2] 2即公共子序列 [1, 2]。这个过程建议自己画一张表感受一下前缀状态是怎么逐格推进的。画过一张表之后你对二维 DP 的理解能上一个台阶。3.2 滚动数组空间 O(nm) 降到 O(m)二维 dp 的开销是 O(nm)当两个字符串长度都在 5000 甚至 10000 以上时内存可能直接爆掉。好在每次更新 dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1] 这三个位置也就是只依赖上一行和当前行所以可以只用两行滚动。思路是用 cur[j] 表示当前行的状态pre[j] 表示上一行的状态。核心难点是dp[i-1][j-1] 在上一轮更新 cur 时已经被覆盖掉了需要在被覆盖之前保存下来。int lcs_scroll(const string a, const string b) { int n a.size(), m b.size(); vectorint pre(m 1, 0), cur(m 1, 0); for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i-1] b[j-1]) { cur[j] pre[j-1] 1; } else { cur[j] max(pre[j], cur[j-1]); } } swap(pre, cur); fill(cur.begin(), cur.end(), 0); } return pre[m]; }注意每次 swap 之后要把 cur 清空不然下一行会残留脏数据。这里用到了一个小技巧在 j 的遍历过程中cur[j-1] 是这一行刚更新的值pre[j] 是上一行的值两者天然可用不需要额外存变量。滚动数组的价值不止在省内存它还能帮助我们理解 DP 的阶段推进本质每一行的更新只需要上一行的完整信息和当前行左侧的最新信息这跟后面的 LCIS 一维优化是一脉相承的思路。3.3 路径还原从右下角反推要输出 LCS 的具体序列可以在二维表中存每个 dp[i][j] 的来源方向也可以直接根据 dp 值反推。更省空间的做法是从右下角 (n, m) 开始如果 a[i] b[j]说明这个字符被匹配了记下它然后 i--, j--否则比较 dp[i-1][j] 和 dp[i][j-1]往值大的方向走。string lcs_path(const string a, const string b) { int n a.size(), m b.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { 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]); } } string res; int i n, j m; while (i 0 j 0) { if (a[i-1] b[j-1]) { res.push_back(a[i-1]); i--; j--; } else if (dp[i-1][j] dp[i][j-1]) { i--; } else { j--; } } reverse(res.begin(), res.end()); return res; }路径还原最容易犯的错是拿 a[i] 和 b[j] 的关系直接决定走向而不看 dp 值。比如 a[i] ! b[j] 时不能感觉上往某个方向走必须严格比较 dp[i-1][j] 和 dp[i][j-1] 的大小因为转移方程里的 max 才是真实依据。当两个方向值相等时往哪个走都会得到一个合法答案但具体输出哪个取决于题目是否要求字典序这个交给你按需选择。3.4 LCS 转 LIS元素互异时的 O(nlogn) 提速LCS 的朴素复杂度是 O(nm)但有一种特殊情况可以提速到 O(nlogn)两个序列的元素都是互异的尤其常见的场景是两个序列都是 1 到 n 的排列。思路是把公共转化为递增。具体做法先遍历 a建立映射 pos[x] x 在 a 中的下标。然后遍历 b把 b[i] 替换成 pos[b[i]]得到一个位置序列 p。如果某个元素没在 a 中出现过它不可能属于公共子序列直接去掉。为什么能这样转因为两个序列公共子序列的长度等于b 中的元素在 a 中出现的下标序列的最长递增子序列长度。递增表示这些元素在 a 中的顺序是保持的而它们本身在 b 中本来就是按顺序出现的于是同时满足两边顺序。最终等价于在置换上求 LIS直接用 2.2 节的二分模板即可。int lcs_to_lis(const vectorint a, const vectorint b) { // a 中元素互异 unordered_mapint, int pos; for (int i 0; i (int)a.size(); i) pos[a[i]] i; vectorint p; for (int x : b) { if (pos.count(x)) p.push_back(pos[x]); } // 对 p 求 LIS vectorint d; for (int x : p) { auto it lower_bound(d.begin(), d.end(), x); if (it d.end()) d.push_back(x); else *it x; } return d.size(); }这里有个隐含陷阱如果 b 中存在重复元素比如 b 里有两个相同的 3映射成两个相同的下标 2、2直接求 LIS 会错误地把两个 3 都选进去因为它们不递增但位置相同。处理方法是把同一元素在 a 中的多个下标按降序排列再展开求 LIS这样能保证同一元素最多被选一次。这个进阶可以等基础版熟练后再研究竞赛里经常考的其实是元素互异的排列场景。4. LCIS把两个模型揉在一起的经典状态设计4.1 状态定义为什么用前缀 以 b[j] 结尾的组合到了 LCIS问题的复杂程度一下子上去因为要同时满足公共和递增两个条件。最直接的想法是 dp[i][j] 表示 a 的前 i 个元素和 b 的前 j 个元素的最长公共递增子序列长度。但这样定义会发现没法转移当你考虑要不要把 a[i] 和 b[j] 都纳入序列时你不知道当前公共递增子序列上一个匹配元素的值是多少无法判断能不能继续递增。公共性用前缀解决了但递增性需要结尾值才能维持。所以经典 LCIS 的状态定义是dp[i][j] 表示 a 的前 i 个元素和 b 的前 j 个元素中以 b[j] 结尾的最长公共递增子序列长度。注意不对称性a 这边用前缀b 这边强制以 b[j] 结尾。为什么选 b[j] 而不是 a[i]因为 b[j] 是当前扫描到的可能匹配候选而 a[i] 是用来作为后缀比较的基准。这个不对称让状态里保留了当前公共子序列末尾是什么值的信息从而能判断递增条件。理解了这一点再回头看 LIS 和 LCS 的状态设计你会发现 LCIS 是两者的自然融合前缀部分继承 LCS 的公共逻辑结尾部分继承 LIS 的递增逻辑。4.2 朴素 O(nm²) 到 O(nm)mx 变量的优化逻辑按状态定义转移可以写成如果 a[i] ! b[j]说明 a[i] 不能作为结尾匹配 b[j]只能继承上一轮的方案dp[i][j] dp[i-1][j]如果 a[i] b[j]说明可以选择把 a[i] 和 b[j] 匹配作为新的结尾。此时需要在前面的 b 序列里找一个 k j满足 b[k] a[i]并且以 b[k] 结尾的公共递增子序列最长然后 dp[i][j] max(dp[i-1][j], max(dp[i-1][k]) 1)朴素实现里每次遇到 a[i] b[j]都要重新遍历一遍 k j复杂度是 O(nm²)n 和 m 到 500 就吃力了。优化的关键点在于当固定 i 时遍历 j 的过程中我们可以用一个 mx 变量维护所有满足 b[k] a[i] 且 k j 的最大 dp[i-1][k] 值。mx 的更新时机非常重要当 b[j] a[i] 时当前这个 b[j] 可以作为后续 a[i] 匹配时的前驱候选所以更新 mx max(mx, dp[i-1][j])。当 b[j] a[i] 时直接用 mx 1 尝试转移。注意同一次循环里一个 b[j] 不可能同时小于又等于 a[i]所以这两个分支天然互斥不会乱套。int lcis_nm(const vectorint a, const vectorint b) { int n a.size(), m b.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { int mx 0; for (int j 1; j m; j) { if (b[j-1] a[i-1]) { mx max(mx, dp[i-1][j]); } else if (b[j-1] a[i-1]) { dp[i][j] max(dp[i-1][j], mx 1); } else { dp[i][j] dp[i-1][j]; } } } int ans 0; for (int j 1; j m; j) ans max(ans, dp[n][j]); return ans; }这里为什么要保留 dp[i][j] max(dp[i-1][j], mx 1) 这层 max因为 dp[i-1][j] 表示不使用 a[i] 的方案mx 1 表示使用 a[i] 作为新结尾的方案。如果 mx 1 还没继承值大说明当前匹配其实不必用 a[i]沿用之前的结果更好。这是 DP 里典型的继承 vs 更新双路径选择千万别省略。mx 优化的本质是把在每个 j 处重新扫描 k的工作提前分摊到一次 j 循环里完成。这跟滑动窗口、前缀最值的思想是一家人理解一次以后遇到类似 DP 优化都不慌。4.3 一维滚动实现空间也压下来LCIS 同样可以做一维滚动优化。因为 dp[i][j] 只依赖 dp[i-1][*]而且转移过程中不涉及跨行交叉引用可以直接把 dp 压成一维数组dp[j] 表示以 b[j] 结尾的 LCIS 长度外层循环每扫描完一个 a[i]dp 数组就被更新到第 i 层的状态。int lcis_1d(const vectorint a, const vectorint b) { int m b.size(); vectorint dp(m 1, 0); for (int x : a) { int mx 0; for (int j 1; j m; j) { if (b[j-1] x) { mx max(mx, dp[j]); } else if (b[j-1] x) { dp[j] max(dp[j], mx 1); } } } return *max_element(dp.begin(), dp.end()); }这段代码短得让人害怕但信息量极大。它把 LCS 的滚动数组思想、LIS 的末尾值决定转移思想全部浓缩在一起。我建议你拿着 4.2 的二维版本和这个一维版本对比着读重点想清楚为什么 dp[j] 在 b[j] x 分支里拿到的还是上一层的值而不会被本层提前污染。答案在 4.1 的状态定义里dp[j] 只有遇到 b[j] a[i] 才会被更新而 b[j] a[i] 时不会所以用它作为 mx 的前驱候选是安全的。4.4 LCIS 的路径还原思路LCIS 输出方案的题比如 POJ 2127要比前两个麻烦一些因为它同时受两个序列约束。思路依然是记录转移来源在一维滚动里额外维护 pre[j] 数组pre[j] 记录 dp[j] 最优转移时上一个匹配的 b 的位置。当 b[j] a[i] 且 dp[j] mx 时记录 last j当前最优前驱位置当 b[j] a[i] 且 mx 1 dp[j] 时更新 dp[j] mx 1pre[j] last。全部扫描完后从 max_element 所在的 j 开始沿着 pre 一路回溯收集 b 中的元素反转即得答案。这里有个细节更新 dp[j] 时要判断 mx 1 dp[j] 才记录 pre否则 pre 可能被一个更差的转移覆盖。如果 mx 1 和 dp[j] 相等pre 记录哪一个都可以但为了可复现稳定起见可以只在严格大于时更新。路径还原题对初学者偏难建议先把长度求对再研究输出千万别一上来就硬怼方案还原。5. 常见问题与调试实录5.1 边界条件下标、初始化、空序列三个模型最常见的翻车点都在边界。第一个是下标。写竞赛代码时我用 1-based 下标dp 数组直接开 n 1 和 m 1这样 dp[0][j] 和 dp[i][0] 天然是 0省去手动处理空序列。但在写 LeetCode 这类 0-based 环境时下标减一的位置特别容易出错我习惯在草稿纸上先标好 a[i-1] 和 b[j-1] 的对应关系再写循环。第二个是初始化。LIS 的 dp[i] 必须初始化为 1不是 0。有些人只把这些 dp 数组默认清 0长度永远是 0答案自然全错。LCS 和 LCIS 则要保证第 0 行、第 0 列是 0这决定了整张 DP 表的地基。第三个是空序列。当 n 0 或 m 0 时三个问题的答案都应该是 0。我的模板里一维 LCIS 的 max_element 在 dp 全 0 时正好返回 0天然安全但如果外层 a 是空的内层压根不会跑也没问题。建议写完代码后手动测一组空输入很多边界 bug 靠这点就能提前揪出来。5.2 lower_bound 和 upper_boundLIS 的严格与不下降这是 LIS 里最具迷惑性的细节。严格递增的 LIS 必须用 lower_bound 替换第一个大于等于当前值的位置最长不下降子序列LNDS要允许相等元素连续出现必须用 upper_bound 替换第一个大于当前值的位置。我刚开始学的时候一直搞反结果在 [2, 2, 2] 这种数组上严格递增版本返回 1不下降版本返回 3两个答案差了整整 2。后来我给自己总结了一句口诀严格递增找大于等于不下降找大于。写代码前先确认题目里是严格递增还是不下降再决定用哪个函数。还有lower_bound 和 upper_bound 要求区间有序正好 d 数组天然严格递增这个前提不会失效。5.3 LCIS 的 mx 更新顺序错一步全盘崩LCIS 一维写法里mx 的更新和 dp[j] 的更新顺序是很多人写不对的地方。我见过一种错误写法在 b[j] a[i] 分支里先更新 dp[j] mx 1然后下一轮遇到 b[j1] a[i] 时又用刚更新的 dp[j] 去更新 mx。这看起来没什么问题但仔细推会发现dp[j] 在本轮已经变成包含 a[i] 作为结尾的新状态了而 mx 要求的候选前驱应该是不包含 a[i]的 dp[i-1][k]只能用上一层的值。如果把新值混进 mx同一个 a[i] 可能被重复使用两次结果必然偏大。所以正确写法是b[j] a[i] 时更新 mx用的是本轮仍未被污染的 dp[j]也就是 dp[i-1][j]b[j] a[i] 时再利用 mx 更新 dp[j]。这两个分支互斥是关键顺序不重要但逻辑边界必须清楚。我建议写代码时加一行注释标记mx 表示当前 b[k] a[i] 的最大 dp[i-1][k]防止三天后自己都不认识这行代码。5.4 路径还原翻车d 数组不是答案回溯要按 dp 值走LIS 里最容易出的笑话是直接把 d 数组当最长递增子序列输出。前面 2.3 节说过d 数组只是辅助长度计算的最小末尾辅助数组里面存的元素可能不是原序列的合法子序列。比如原数组 [2, 1, 3]处理完 d 是 [1, 3]长度 2但 [1, 3] 在原始序列里的顺序是 1 在 3 前面恰好合法换个例子 [3, 1, 2]d 最终是 [1, 2]但 1 到 2 在原序列里也是合法的。看起来好像没问题再换 [2, 5, 3, 4]d 最后是 [2, 3, 4]原序列里 2 在 3 前面也合法。其实 d 数组经常恰好是某个合法 LIS但这不是保证的存在反例。唯一的稳妥办法就是用 idx 数组倒序回溯。LCS 的路径还原反例也很典型有些同学只看字符相等不相等不比较 dp 值就乱走结果中间多走一步或少走一步输出一个不连续的序列。正确做法是字符相等走对角线字符不等比较 dp[i-1][j] 和 dp[i][j-1]严格取大的方向。5.5 调试小技巧打表 对拍最后分享一个实战中特别高效的调试方法。当你怀疑 DP 转移写错了别急着改先打印一张 DP 表。代码里临时加两层循环把 dp[i][j] 全部输出然后用纸笔手动计算一个小例子跟程序输出逐格对比。我会拿 3x4 这种极小规模的数据比如 a [1, 2, 3]b [2, 1, 3, 4]把表打出来哪一格错了立刻暴露。对于优化版本我还建议准备一个朴素的 O(n²) 或 O(nm²) 的实现写个随机数据对拍脚本。优化版和朴素版跑同样的数据结果不一致就说明你的优化引入了 bug。这个对拍习惯我从学算法初期保持到现在救了我无数次。6. 序列模型还能用到哪里6.1 竞赛与面试中的高频变体这三个模型在算法竞赛里几乎是必考内容。LIS 的直接考法包括洛谷 P1020 导弹拦截这类最长不上升子序列 贪心的组合题以及各种二维偏序问题。LCS 的经典题是 LeetCode 1143面试手撕频率极高。LCIS 相对小众但如果把三个模型放在同一道综合题里往往就是拉开差距的地方。有个组合思路值得重点研究先求双端 LIS。比如合唱队形问题要求选出一个先递增后递减的最长子序列做法是先正着求每个位置结尾的 LIS 长度再反着求每个位置开始的下降子序列长度相当于从右往左的 LIS然后枚举中间最高点两个长度相加减 1。这类题本质上是把 LIS 模型用两次。6.2 现实场景diff、基因比对、调度LCS 在现实世界的应用最直观。文本 diff 工具的核心就是 LCS 算法它找出两份文本最长不变的部分剩下部分就是增删区域。基因序列比对里DNA 片段被视为字符序列LCS 用来衡量两条序列的相似度。LIS 则像有序调度的影子比如一个项目有多道工序每道工序有开始时间和结束时间求最多能按顺序完成多少个互不冲突的工序本质上就是按结束时间排序后的 LIS 问题。LCIS 相对竞赛化但理解它能帮你建立多约束 DP的感觉对解决复杂的依赖型规划问题很有帮助。6.3 一道自测综合题检验掌握程度如果你想验证自己是不是真的吃透了这三个模型可以试试这道自测题给定两个长度不超过 500 的序列 a 和 b求它们的最长公共递增子序列并且输出方案。动手前先别翻代码自己从头推一遍状态定义、转移方程、mx 优化、pre 回溯然后拿 [1, 2, 3, 4] 和 [2, 3, 4, 1] 验证结果是否为 [2, 3, 4]。能把这道题一遍写对说明你对三个模型的理解已经过关了。个人实操后的几点体会我把这三个模型写熟了之后最大的感悟是动态规划的最大难点不在方程而在状态定义。LIS 用以 i 结尾存储递增信息LCS 用前缀存储公共信息LCIS 则是两种状态语言的杂交。任何一个状态定义解释不清为什么这样设后面所有的转移都像是背模板。学 DP 别怕慢推一个小例子的收获远超看十遍别人的题解。最后再分享一个习惯我在本地维护了一份DP 模板速查笔记LIS、LCS、LCIS 各存一份朴素版、一份优化版、一份带路径版比赛前扫一眼面试前扫一眼。这份笔记后来也成了朋友之间流传最广的东西——把三个模型放在一页里对比着看会比单个零散记忆牢固得多。