1. 从字符串“找相同”到最长公共子序列先问一个很实际的问题你写代码的时候有没有用过git diff来看两个版本之间改了哪些内容它的核心逻辑之一就是找出两个文本的“相同部分”和“差异部分”——这个“相同部分”的数学抽象就是最长公共子序列Longest Common Subsequence简称 LCS。我第一次接触到 LCS 是在准备算法面试的时候当时刷到这道题的第一反应是“这不就是找两个字符串里相同的最长串吗”结果被现实教育了一通——子序列Subsequence和子串Substring完全不是一回事。子串要求字符在原文里是连续的而子序列只要求字符的相对顺序一致中间允许跳过任意数量的字符。举个例子abcde和ace如果找最长公共子串答案是空或者单个字符但找最长公共子序列答案是ace长度是 3。LCS 的价值远不止一道面试题。从代码的 diff 工具、DNA 序列比对、到文本查重、拼写纠错甚至是你每天都在用的版本管理系统背后都有它的影子。本文会从零开始把这道题从暴力递归到动态规划逐步拆解再聊到空间优化和真实场景里的工程实现让你不仅会做题更明白它为什么这么设计、到底能用在哪里。这篇文章适合以下几类人正在准备算法面试、想彻底吃透动态规划的读者工作中要处理文本比对、版本差异、序列分析的后端或算法工程师对算法如何落地到真实系统感到好奇、想建立“从题目到工程”思维的人。2. 理解问题子序列的定义与暴力枚举思路2.1 子序列 vs 子串一字之差思路完全不同先做一个精确的定义。给定一个字符串s它的子序列就是从s中删除零个或多个字符不改变剩余字符的相对顺序后得到的新字符串。注意关键词不改变相对顺序。所以ace是abcde的子序列因为你可以把abcde中的b和d删掉剩下的a c e相对顺序没变。但如果问aec是不是abcde的子序列不是因为e在a后面没错但在c前面就不对了原串里e的位置在c后面你没法通过删除字符来改变它们的先后关系。子串则严格得多它要求字符在原字符串中连续出现。abc是abcde的子串因为它在原串里挨在一起ace不是abcde的子串因为中间隔了字符。这个区别直接决定了题目的难度。找最长公共子串可以用滑动窗口或者后缀数组而找最长公共子序列因为允许跳过字符搜索空间呈指数级扩散本质上是一个组合优化问题。2.2 枚举所有子序列指数级复杂度完全不可行如果让你用最原始的方法解决 LCS你会怎么做把第一个字符串的所有子序列都枚举出来然后逐个检查是不是第二个字符串的子序列最后挑最长的那个。一个长度为 n 的字符串子序列总数是 2^n 个每个字符要么选、要么不选。当 n20 的时候是 100 多万n50 的时候是千万亿级别n100 的时候已经是天文数字。所以说暴力枚举只适合用来理解问题绝对不适合用来解题。那怎么避免指数爆炸核心观察是LCS 问题具有“最优子结构”和“重叠子问题”两个特征这正是动态规划最擅长的领域。我先用一种更直观的方式来建立直觉再看怎么把它翻译成代码。2.3 从“末尾字符”看问题划分成三种情况人类解决 LCS 的直觉其实很简单。站在两个字符串的末尾往前看假设有两个字符串s1和s2我们想看它们的最长公共子序列有多长那就要先看它们的最后一个字符。如果s1的最后一个字符和s2的最后一个字符相同那这个字符一定可以出现在某个最长公共子序列里。为什么因为它是末尾字符不影响前面字符的相对顺序把它用上一定能增加长度、不会亏。此时问题就变成了「在各自去掉末尾字符的两个字符串中找 LCS然后加 1」。如果最后一个字符不相同那么这个字符不可能同时成为 LCS 的末尾因为它们俩就不一样所以答案只能从两个候选里取较大值「去掉s1的末尾字符」后的 LCS或者「去掉s2的末尾字符」后的 LCS。这个推理过程可以用一句话概括LCS 的长度等于“末尾字符相同处理办法”和“末尾字符不同处理办法”中递归出来的最优解。这种从末尾开始倒着思考问题的方式就是动态规划状态转移方程的雏形。3. 动态规划核心拆解状态定义、转移方程与边界条件3.1 为什么暴力递归会“重复计算”顺着上面的思路把递归关系写出来会非常自然LCS(i, j) 0, 如果 i 0 或 j 0 1 LCS(i-1, j-1), 如果 s1[i] s2[j] max(LCS(i-1, j), LCS(i, j-1)), 如果 s1[i] ! s2[j]其中i和j分别代表s1的前 i 个字符和s2的前 j 个字符。这个递归本身没错但它会把同一个子问题反复算很多遍。比如LCS(3, 4)可能从LCS(2, 4)和LCS(3, 3)两条路都走到而这两条路又都会继续往下分裂。在一棵指数级别的递归树里大量节点是重复的。这就像你在一个大仓库里找一件东西每次需要“从某个区间的某个位置开始找”的时候你都重新走一遍而不是把结果记下来。人当然不会这么傻代码也不应该这么写。3.2 状态定义与完整推导动态规划的思路就是把递归改成自底向上的填表过程。先定义状态dp[i][j]表示s1的前 i 个字符构成的子串与s2的前 j 个字符构成的子串它们的最长公共子序列的长度。这里有一个容易混淆的点dp[i][j]的i和j是“长度”不是“下标”。也就是说s1的前 i 个字符是s1[0...i-1]s2的前 j 个字符是s2[0...j-1]。很多新手在写代码的时候会搞混要么把表开小了要么循环里取字符时越界。记住dp 表的维度是(len11) × (len21)多加的一行一列留给空串。边界条件也很明确当i0或j0时也就是其中一个字符串是空串公共子序列必然是空长度是 0。所以dp[0][j] 0dp[i][0] 0这也是为什么 dp 表第一行第一列都是 0。接下来是转移方程分两种情况当s1[i-1] s2[j-1]说明当前这两个字符可以成为公共子序列的一部分所以dp[i][j] dp[i-1][j-1] 1当s1[i-1] ! s2[j-1]说明当前这两个字符不能同时入选那答案要么来自s1去掉当前字符后的最优解要么来自s2去掉当前字符后的最优解取较大值即dp[i][j] max(dp[i-1][j], dp[i][j-1])。为什么最后一个字符相同的时候可以直接1因为这两个字符相等把它们放在公共子序列的末尾不会跟前面的选择冲突而且任何“公共子序列”最多只能包含每个字符串的一个末尾字符所以直接把当前字符接上是最优的。这个“贪心”在 LCS 里是安全的但注意这个安全成立的前提是前面的子序列已经是最优。3.3 填表过程可视化为什么必须按行遍历用s1 abcde和s2 ace来手动填一遍表。两个字符串的长度分别是 5 和 3所以 dp 表是 6 行 4 列多出的行和列是空串的 0。初始第一行和第一列全是 0。然后按行从左到右填。这里我直接给一个关键结论dp 表里每个格子的值只依赖它左上角、正上方、正左方这三个格子所以在循环时只要保证先行后列、从上到下从左到右地填充每个格子的前置依赖一定已经计算过了。 a c e 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 e 0 1 2 3表格右下角的3就是最长公共子序列的长度。你从右下角回溯如果s1[i-1] s2[j-1]这个字符就属于 LCS 的一部分向左上移动如果不相等看dp[i-1][j]和dp[i][j-1]谁大就往哪边移动。这样就能还原出ace。再举一个不对称的例子s1 abcd,s2 bc。公共子序列是bc长度 2。你填表后会观察到dp的值在首行首列之外是“非递减”的这很符合直觉——字符越多公共子序列最长只会更长或持平不可能变短。3.4 时间复杂度与空间复杂度分析填一张(m1) × (n1)的表每个格子只做常数次比较所以时间复杂度是 O(mn)空间复杂度也是 O(mn)。对于字符串长度在几千以内的场景这个空间开销完全可接受。但如果两个文本各有一万行代码dp 表的规模就是一亿个格子——几百 MB 的内存直接爆掉。这时候就需要空间优化方案我在第 5 章节会专门讲。提示面试中问到“能不能进一步优化空间复杂度”是非常常见的追问别只背 O(mn) 的解法请把滚动数组的方法也掌握扎实。4. 代码实现从二维 DP 到一维滚动数组优化4.1 标准的二维 DP 实现先用最标准的二维数组实现突出一个“稳”字。语言我用的是 Go这套逻辑切换成 Python、C、Java 都很简单func longestCommonSubsequence(s1, s2 string) int { m, n : len(s1), len(s2) dp : make([][]int, m1) for i : range dp { dp[i] make([]int, n1) } for i : 1; i m; i { for j : 1; j n; j { if s1[i-1] s2[j-1] { dp[i][j] dp[i-1][j-1] 1 } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]) } } } return dp[m][n] } func max(a, b int) int { if a b { return a } return b }这段代码有几个容易出错的点循环从1开始到m/n结束因为第 0 行第 0 列代表空串取字符时用的是s1[i-1]而不是s1[i]因为i代表长度很多人 debug 半天找不到越界或者结果差 1问题就出在这里函数内部没有对空字符串做特殊处理但依赖dp表初始化为 0 的逻辑自动覆盖了空串边界。4.2 空间优化为什么可以只用两行仔细观察状态转移方程dp[i][j]只和dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]有关。换句话说当前行的计算只需要上一行的数据和当前行左侧已经算出的数据更早的行在算完之后就再也不会被用到了。所以可以只保留两行数组算完一行就丢弃上一行。这种技巧叫“滚动数组”。如果题目只需要长度、不需要还原具体子序列这是最常用的优化方案func longestCommonSubsequenceOptimized(s1, s2 string) int { m, n : len(s1), len(s2) prev : make([]int, n1) cur : make([]int, n1) for i : 1; i m; i { for j : 1; j n; j { if s1[i-1] s2[j-1] { cur[j] prev[j-1] 1 } else { cur[j] max(prev[j], cur[j-1]) } } prev, cur cur, prev // 注意交换后cur 里还是旧数据要在每轮循环里覆盖 } return prev[n] }这里有个坑每次内层循环结束后交换prev和cur下一轮开始的时候cur里残留着上一轮的数据如果哪一格没被赋值就会出问题。但好在外层循环每一轮都会把cur的所有下标从 1 到 n 重新赋值一遍所以逻辑上是安全的。唯一要留意的是cur[0]始终是 0这个值在循环里不会变符合边界条件。4.3 继续优化到一维数组难点在于左上角的值既然只用上一行和当前行那是不是可以直接用一维数组只保留一行一边遍历一边覆盖可以的但有一个细节特别容易翻车。一维数组dp[j]在更新时代表的是“当前行第 j 列”的值。当我们计算dp[j]时需要三个值dp[j-1]当前行左侧的旧值不对注意dp[j-1]在 j 循环里已经先被更新过了所以它代表的是当前行第 j-1 列的新值也就是dp[i][j-1]这个是正的dp[j]还没被当前行覆盖它还是上一行第 j 列的值也就是dp[i-1][j]也是正的dp[i-1][j-1]也就是上一行的j-1位置这个值在dp[j-1]被覆盖的时候就已经丢了。所以关键问题来了当s1[i-1] s2[j-1]时要使用dp[i-1][j-1]但一维数组里这个值已经被覆盖了。解决办法是在每次内层循环里用一个临时变量保存“上一行的 j-1 格”func longestCommonSubsequenceOneDim(s1, s2 string) int { n : len(s2) dp : make([]int, n1) for i : 1; i len(s1); i { prevDiagonal : 0 // 初始为 dp[j-1] 的上一行值即 dp[i-1][0]是 0 for j : 1; j n; j { temp : dp[j] // 保存当前格子的旧值这是下一轮循环的 prevDiagonal if s1[i-1] s2[j-1] { dp[j] prevDiagonal 1 } else { dp[j] max(dp[j], dp[j-1]) } prevDiagonal temp } } return dp[n] }这段代码是面试高频考点。你不需要在面试时背它只要理解了prevDiagonal保存的是“上一行 j-1 的值”就永远不会写错。它相当于把二维表格压成了一条线用“在前一个格子被覆盖之前先把它存起来”的方式保住了那个唯一的必须用到的旧值。4.4 不只求长度如何还原最长公共子序列本身很多时候我们不仅需要长度还需要知道 LCS 到底是哪一个字符串。比如你要在 diff 工具里展示两个版本共同保留的部分就必须还原出具体的子序列。还原过程要用到完整的 dp 表因为你需要在整个表上回溯。算法思路如下从dp[m][n]开始往回走如果s1[i-1] s2[j-1]说明这个字符入选把它记录下来然后i--, j--如果不等那就对比dp[i-1][j]和dp[i][j-1]谁大往谁那边走如果相等任选一边即可这说明存在多个不同的 LCS方向选择会影响最终还原出哪一个。用s1 abcde、s2 ace来走一遍走到dp[5][3]3先看e e入选e到dp[4][2]d ! cdp[4][2]和dp[3][2]都是 2任选一边最终能还原出ace。如果把s1换成aebdc你会发现aec和abc都是合法的 LCS长度一样内容不同。这一点在工程上很重要——两个文本的 diff 结果不唯一展示了“哪一种共同保留部分”取决于你回溯方向的优先级。5. 复杂度进阶位运算并行化与典型实际应用场景5.1 当字符串超长时m 远大于 n 的处理策略前面提到一维数组可以把空间从 O(mn) 降到 O(n)但那是在 m 和 n 差不多大的时候。如果其中一个字符串特别长比如一个 100 万字的长文本和一个 100 字的短短语找 LCS那我们可以把短的那条串作为 n长的那条作为 m空间只开 n 的长度。代码里只需要在最初比较两个字符串的长度如果len(s1) len(s2)就交换保证外层循环是长串、内层循环是短串这样一维 DP 的内层数组永远是 O(短串长度)。这种“内层选短的”的策略在工程里很常用不止 LCS像 Edit Distance 这类带网格的 DP 问题同样适用。5.2 位运算并行化一种比较少见的加速技巧有一种针对小字符集的高性能优化把字符集映射成位掩码然后用位运算同时处理 64 个位置的匹配情况。具体做法是先对每个字符记录它在短串中出现的位置集合用一个 64 位的整数mask[c]标注某个字符出现在短串的哪些位置然后遍历长串用一段优化的位操作更新状态。这个算法能把复杂度从 O(mn) 压到 O(m × n/64)原理是每次迭代同时处理了一个 64 位机器字里多个位置的“匹配—传播”过程。实际工程里像基因序列比对这种对速度要求极高的场景会用到这类并行化技巧。对于普通业务场景一维滚动数组已经足够不必过早追求这种在位运算层面才有的加速。真要深入推荐阅读专门讲“Bitap 算法”和“BLAST 序列比对”的资料LCS 的位运算版本是它们的近亲。5.3 应用场景一代码 diff 与版本控制git diff的核心算法虽然做了很多工程化变形但其根基就是 LCS。两个文件版本分别视为一个字符串序列按行切分求出它们的公共子序列后不在公共子序列里的行就是新增或删除的行。因为 LCS 不唯一diff 工具会通过权重调整来让输出更“人类友好”——比如尽量让删除和新增成对出现避免大面积的行重新排序。有一个很常见的误区很多人觉得 diff 需要的是“最长公共子串”因为看到 diff 输出里大片的连续相同行。实际上连续相同的行是公共子串但它只是公共子序列的特例按行比对时连续的行在序列意义上也是连续的所以两者表现一致。但真正决定 diff 正确性的还是 LCS 逻辑否则一次插入一个空行就会导致整个文件被判定为全部重写。5.4 应用场景二文本相似度与查重把两个文本的 LCS 长度除以某种归一化分母通常是两个文本中较长者的长度可以得到一个相似度指标。比如在两段代码的抄袭检测场景中系统会先做 token 化或按行切分再算 LCS相似度超过阈值就标记。这里要注意LCS 相似度对“文本内字符顺序被整体打乱”的情况完全无感——你把两个段落调换顺序LCS 可能会发生剧烈变化。所以工程上通常不会只用 LCS 一个指标判断重复而是结合 N-gram 重叠、编辑距离等一起做。我在实际项目中见过有人只拿 LCS 做查重结果两份结构不同但完全复制的文档没被查出来因为 LCS 对“被插入大量干扰字符”的敏感度不高。这个坑要提前规避。5.5 应用场景三生物信息学中的序列比对DNA 序列本质就是A/T/C/G组成的超长字符串。两个基因序列的公共子序列长度在生物信息学里对应着“同源片段”的长度估计。真实的序列比对算法如 Needleman-Wunsch其实是在 LCS 基础上加入了替换惩罚和空位惩罚的加权版本相当于更一般化的全局比对问题。这类场景中字符串长度可以达到数百万量级DP 的 O(mn) 复杂度就撑不住了所以工业界会使用启发式算法如 BLAST先快速定位高相似度的种子片段再在局部做精确比对。这给我们一个启发算法题里的标准解法是“精确且正确”的范式但真实系统往往需要在正确性和性能之间做取舍。6. 工程实践如何用 LCS 做一个简易的文本差异化工具6.1 需求拆解不只是算长度还要输出“差异块”纯算 LCS 长度其实没多少工程价值真正有用的是输出哪些行是公共的、哪些行是新增的、哪些行是删除的。我来设计一个迷你 diff 工具。输入是两个字符串按\n切分成行数组然后用二维 DP 求出 LCS 的行索引映射回溯时输出三种标记common公共行、deleted只在旧文本中出现的行、added只在新增文本中出现的行。这里的关键点在于我们要的不是“公共子序列的长度”而是“哪些行在公共子序列里”。所以 DP 表必须完整保留不能使用空间优化的一维数组——因为回溯阶段需要任意访问历史状态。6.2 具体实现步骤先写一个生成 DP 表的函数func buildDPTable(lines1, lines2 []string) [][]int { m, n : len(lines1), len(lines2) dp : make([][]int, m1) for i : range dp { dp[i] make([]int, n1) } for i : 1; i m; i { for j : 1; j n; j { if lines1[i-1] lines2[j-1] { dp[i][j] dp[i-1][j-1] 1 } else { if dp[i-1][j] dp[i][j-1] { dp[i][j] dp[i-1][j] } else { dp[i][j] dp[i][j-1] } } } } return dp }注意在回溯时可能会遇到dp[i-1][j] dp[i][j-1]的情况此时我选择优先往上走视为deleted这样 diff 的输出会更稳定不会因为方向瞎跳导致结果时对时错。然后是回溯函数type DiffLine struct { Kind string // common / deleted / added Text string } func backtrack(lines1, lines2 []string, dp [][]int) []DiffLine { i, j : len(lines1), len(lines2) var result []DiffLine for i 0 j 0 { if lines1[i-1] lines2[j-1] { result append(result, DiffLine{common, lines1[i-1]}) i-- j-- } else if dp[i-1][j] dp[i][j-1] { result append(result, DiffLine{deleted, lines1[i-1]}) i-- } else { result append(result, DiffLine{added, lines2[j-1]}) j-- } } for i 0 { result append(result, DiffLine{deleted, lines1[i-1]}) i-- } for j 0 { result append(result, DiffLine{added, lines2[j-1]}) j-- } // 因为是从尾往头回溯的最后要反转 reverse(result) return result }这个实现和git diff的输出方向不太一样它是从末尾往前收集、最后反转。核心逻辑就是如果当前两行相等归为公共行如果不相等看 dp 表决定是“删除旧行的内容”还是“加入新行的内容”。6.3 实测一下假设我们有两个版本旧版本function hello() { console.log(hello); }新版本function hello() { const msg hello; console.log(msg); }按行切分后console.log(hello);是公共的其他行会有增删。你运行上面代码后会得到类似下面的输出common function hello() { deleted console.log(hello); added const msg hello; added console.log(msg); common }注意这里的顺序看起来有点怪console.log(hello);被标记删除console.log(msg);被标记新增虽然它们语义上很像但 LCS 是按“完全相等”来匹配行的。如果你想让 diff 更聪明识别出hello变成了msg那是语义 diff 的范畴需要更高层次的 AST 解析LCS 本身不负责这件事。6.4 性能与内存什么时候需要分块处理上面这个简易 diff 是 O(mn) 时间和 O(mn) 空间的。如果两个文件各有 5000 行dp 表就是 2500 万个格子内存大约 200 MB每个 int 8 字节。这在真实工程里就有点吃不消了。实用的降内存方案是分块先用哈希找到两边完全相同的“锚点行”通常是空行、大括号行、独有特征行把大文件切成若干小块每个小块内部再跑完整 DP。这个思路是 Myers diff 算法的前置近似也是很多真实 diff 工具的优化方向之一。如果你只是写个小工具自己用可以先不优化如果要用到生产环境分块几乎是必须的。6.5 工程实现的常见误区第一不要拿字符串作为 dp 表里比较的最小单位除非你明确知道行为粒度。如果按字符比较大文件 diff 会慢到无法使用。按行比较每一行是一个原子然后行内部再做二次 diff比如列级 diff这种分层策略是文本比对工具的标准做法。第二回溯方向会影响输出稳定性。我见过同事写的 diff 工具在相同输入下来回变化就是因为 dp 值相等时选择的回溯方向不稳定。解决办法是固定一个优先级比如“优先删旧行”——这样输出永远确定。第三注意换行符差异。Windows 的\r\n和 Linux 的\n会让每一行看起来不一样导致 diff 结果全是增删。切分前先把\r去掉这是基础中的基础。7. 面试避坑指南状态压缩的隐藏细节与相似题目串联7.1 面试官真正想考察什么LCS 在面试里高频出现不只是因为它解法经典更因为它能考察多个维度边界处理、空间优化意识、回溯还原能力、以及迁移能力变体题能不能套用同一套 DP 框架。很多候选人能把二维 DP 默写出来但一问“为什么转移方程里相等时用dp[i-1][j-1] 1而不是dp[i-1][j] 1”“不相等时为什么不是max(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])”“一维数组优化时那个被覆盖的左上角值怎么保存”这三个问题能答上来的人才算真正理解了这道题而不是背了个模板。第一个问题的答案前面已经说过第二个问题值得多说一句dp[i-1][j-1]其实被dp[i-1][j]和dp[i][j-1]间接包含了——因为 dp 值非递减dp[i-1][j]一定不小于dp[i-1][j-1]dp[i][j-1]同理所以那个三项的 max 等价于两项的 max。面试时能指出这一点是加分项。7.2 相似题对比LCS、编辑距离、最长递增子序列我强烈建议把这三道题放在一起对比学习因为它们共享同一个 DP 骨架只是转移方程的细节不同LCS相等时dp[i-1][j-1] 1不等时取max(dp[i-1][j], dp[i][j-1])编辑距离Edit Distancedp[i][j]表示把s1[0..i-1]变成s2[0..j-1]的最少操作数转移时考虑增、删、改三操作取三者最小值最长递增子序列LIS一维 DPdp[i]表示以第 i 个元素结尾的最长递增子序列长度转移时向前扫描所有j i且nums[j] nums[i]或使用二分优化到 O(n log n)。把它们放在一起看你会发现自己掌握了“动态规划自底向上的通用填表框架”定义状态、找转移、定边界。剩下的就是在具体问题上做出不同的选择判断。7.3 关于“多个 LCS 输出”的经典陷阱如果题目问“请输出所有可能的最长公共子序列”难度瞬间上升。因为回溯时遇到dp[i-1][j] dp[i][j-1] dp[i][j]的岔路两条路都要走这就从单路径回溯变成了 DFS 枚举最坏情况下输出量本身就是指数级的。面试中建议先和面试官确认输出数量限制同时设计去重策略比如用哈希集合存中间结果避免重复递归。去重的常用方法是“按位置去重”在 DFS 回溯时记录当前走到(i, j)以及已经拼出的后缀结果如果同一(i, j)曾经用相同的后缀访问过就剪枝。这个优化可以把大量重复分支剪掉但对极端构造的场景仍然会爆炸因为合法答案数量本身是指数级的。7.4 刷题节奏建议如果 LCS 是你接触的第一个动态规划题目我的建议是这样的学习路径先手写暴力递归版本体会指数爆炸加一个 memo 数组改成自顶向下记忆化搜索改写成自底向上的二维 DP改写成滚动数组一维版本最后实现回溯还原子序列。每一层改动都亲手编译、运行、测试。很多人在第二步就跳过直接背第四步结果面试时被问到“为什么这么写”就卡住了。就我个人的体会这五步走一遍比刷十道 DP 题效率都高因为你在过程中反复体验的是同一种计算模式的自洽和边界约束而不是孤立地背结论。8. 实操心得与下一步扩展方向8.1 我踩过的几个坑第一dp 表初始化陷阱。二维切片在 Go 里必须逐行make我一开始想当然地以为二维数组可以一次性make([][]int, m1, n1)结果跑起来直接 panic——这是切片嵌套的结构不是真正的二维数组。这在 C/Java 里不常见但在 Go 和 Python二维列表里特别容易踩。第二字符相等时直接1的“贪心直觉”。我曾经在相等的情况下写成dp[i][j] dp[i-1][j] 1因为觉得“既然当前字符相等那就在上一行的基础上加 1 就行了”——这是错的。你要加上去的那个字符必须接在s1和s2都去掉当前字符后的最优序列后面也就是dp[i-1][j-1] 1。写成dp[i-1][j]意味着你跳过了s2的当前字符但你又用了这个字符逻辑上自相矛盾。第三回溯时忘了把结果反转。回溯是从表尾走向表头收集的字符天然是倒序。如果你忘了reverse会输出一个完全反向的 LCS。签名是dp[m][n]不是dp[len(s1)][len(s2)]的这种低级错误我就不多说了写代码时把长度变量命名为m, n并且严格区分“长度”和“下标”是减少这种错误最有效的办法。8.2 后续可以这样扩展如果你想把 LCS 吃透并且让它发挥更大价值我建议往这几个方向延伸Myers diff 算法这是git diff真正使用的核心算法它的思路是用编辑脚本的路径搜索代替 DP 填表在“两个文件大部分相同”时时间复杂度接近 O(ND)远快于 O(mn)。理解 Myers 算法之后再看 LCS会有一种“原来 DP 只是其中一种实现”的豁然感。加权序列比对在 LCS 基础上引入替换、插入、删除的不同代价就变成了序列比对里的经典全局比对问题。生物信息学里的 Needleman-Wunsch 算法就是这个版图里的一员搞懂它以后你会把“字符串相同”的思维升级成“字符串相似”的思维。多序列比对两个序列的 LCS 很容易但三个及以上序列找公共子序列就是 NP-hard 了工业界用的都是启发式算法。从这个点出发你能理解“为什么很多真实的复杂问题不能只靠一道算法题解决”。8.3 最后说一句大实话动态规划这个板块很多人是“背着背着就过了”但 LCS 这道题特别适合做理解 DP 的锚点因为它简单到状态定义一句话就能说清又深刻到能延展出 diff、比对、并行优化这些工程话题。我见过不少同事在项目里遇到文本比对需求时第一反应是去找第三方库完全没有意识到自己可以在一晚上写出一个可用的精简版——实际上掌握了 LCS 的 DP 表加回溯就能覆盖一大部分真实需求了。如果你正在准备面试建议把 LCS 的“五步进阶法”亲手走一遍如果你是在做工程建议直接把我前面那个迷你 diff 的代码跑一下然后加上分块优化你会对版本控制工具底层多一份实实在在的理解。算法题和工程实现之间的鸿沟往往就是从“我理解了”到“我能写出来还能讲清楚为什么这么写”之间拉开的。 
长河君 · 2026/10/19 6:34:15 · 阅读 1.2k 最长公共子序列（LCS）从动态规划到工程实践深度解析
1. 从字符串“找相同”到最长公共子序列先问一个很实际的问题你写代码的时候有没有用过git diff来看两个版本之间改了哪些内容它的核心逻辑之一就是找出两个文本的“相同部分”和“差异部分”——这个“相同部分”的数学抽象就是最长公共子序列Longest Common Subsequence简称 LCS。我第一次接触到 LCS 是在准备算法面试的时候当时刷到这道题的第一反应是“这不就是找两个字符串里相同的最长串吗”结果被现实教育了一通——子序列Subsequence和子串Substring完全不是一回事。子串要求字符在原文里是连续的而子序列只要求字符的相对顺序一致中间允许跳过任意数量的字符。举个例子abcde和ace如果找最长公共子串答案是空或者单个字符但找最长公共子序列答案是ace长度是 3。LCS 的价值远不止一道面试题。从代码的 diff 工具、DNA 序列比对、到文本查重、拼写纠错甚至是你每天都在用的版本管理系统背后都有它的影子。本文会从零开始把这道题从暴力递归到动态规划逐步拆解再聊到空间优化和真实场景里的工程实现让你不仅会做题更明白它为什么这么设计、到底能用在哪里。这篇文章适合以下几类人正在准备算法面试、想彻底吃透动态规划的读者工作中要处理文本比对、版本差异、序列分析的后端或算法工程师对算法如何落地到真实系统感到好奇、想建立“从题目到工程”思维的人。2. 理解问题子序列的定义与暴力枚举思路2.1 子序列 vs 子串一字之差思路完全不同先做一个精确的定义。给定一个字符串s它的子序列就是从s中删除零个或多个字符不改变剩余字符的相对顺序后得到的新字符串。注意关键词不改变相对顺序。所以ace是abcde的子序列因为你可以把abcde中的b和d删掉剩下的a c e相对顺序没变。但如果问aec是不是abcde的子序列不是因为e在a后面没错但在c前面就不对了原串里e的位置在c后面你没法通过删除字符来改变它们的先后关系。子串则严格得多它要求字符在原字符串中连续出现。abc是abcde的子串因为它在原串里挨在一起ace不是abcde的子串因为中间隔了字符。这个区别直接决定了题目的难度。找最长公共子串可以用滑动窗口或者后缀数组而找最长公共子序列因为允许跳过字符搜索空间呈指数级扩散本质上是一个组合优化问题。2.2 枚举所有子序列指数级复杂度完全不可行如果让你用最原始的方法解决 LCS你会怎么做把第一个字符串的所有子序列都枚举出来然后逐个检查是不是第二个字符串的子序列最后挑最长的那个。一个长度为 n 的字符串子序列总数是 2^n 个每个字符要么选、要么不选。当 n20 的时候是 100 多万n50 的时候是千万亿级别n100 的时候已经是天文数字。所以说暴力枚举只适合用来理解问题绝对不适合用来解题。那怎么避免指数爆炸核心观察是LCS 问题具有“最优子结构”和“重叠子问题”两个特征这正是动态规划最擅长的领域。我先用一种更直观的方式来建立直觉再看怎么把它翻译成代码。2.3 从“末尾字符”看问题划分成三种情况人类解决 LCS 的直觉其实很简单。站在两个字符串的末尾往前看假设有两个字符串s1和s2我们想看它们的最长公共子序列有多长那就要先看它们的最后一个字符。如果s1的最后一个字符和s2的最后一个字符相同那这个字符一定可以出现在某个最长公共子序列里。为什么因为它是末尾字符不影响前面字符的相对顺序把它用上一定能增加长度、不会亏。此时问题就变成了「在各自去掉末尾字符的两个字符串中找 LCS然后加 1」。如果最后一个字符不相同那么这个字符不可能同时成为 LCS 的末尾因为它们俩就不一样所以答案只能从两个候选里取较大值「去掉s1的末尾字符」后的 LCS或者「去掉s2的末尾字符」后的 LCS。这个推理过程可以用一句话概括LCS 的长度等于“末尾字符相同处理办法”和“末尾字符不同处理办法”中递归出来的最优解。这种从末尾开始倒着思考问题的方式就是动态规划状态转移方程的雏形。3. 动态规划核心拆解状态定义、转移方程与边界条件3.1 为什么暴力递归会“重复计算”顺着上面的思路把递归关系写出来会非常自然LCS(i, j) 0, 如果 i 0 或 j 0 1 LCS(i-1, j-1), 如果 s1[i] s2[j] max(LCS(i-1, j), LCS(i, j-1)), 如果 s1[i] ! s2[j]其中i和j分别代表s1的前 i 个字符和s2的前 j 个字符。这个递归本身没错但它会把同一个子问题反复算很多遍。比如LCS(3, 4)可能从LCS(2, 4)和LCS(3, 3)两条路都走到而这两条路又都会继续往下分裂。在一棵指数级别的递归树里大量节点是重复的。这就像你在一个大仓库里找一件东西每次需要“从某个区间的某个位置开始找”的时候你都重新走一遍而不是把结果记下来。人当然不会这么傻代码也不应该这么写。3.2 状态定义与完整推导动态规划的思路就是把递归改成自底向上的填表过程。先定义状态dp[i][j]表示s1的前 i 个字符构成的子串与s2的前 j 个字符构成的子串它们的最长公共子序列的长度。这里有一个容易混淆的点dp[i][j]的i和j是“长度”不是“下标”。也就是说s1的前 i 个字符是s1[0...i-1]s2的前 j 个字符是s2[0...j-1]。很多新手在写代码的时候会搞混要么把表开小了要么循环里取字符时越界。记住dp 表的维度是(len11) × (len21)多加的一行一列留给空串。边界条件也很明确当i0或j0时也就是其中一个字符串是空串公共子序列必然是空长度是 0。所以dp[0][j] 0dp[i][0] 0这也是为什么 dp 表第一行第一列都是 0。接下来是转移方程分两种情况当s1[i-1] s2[j-1]说明当前这两个字符可以成为公共子序列的一部分所以dp[i][j] dp[i-1][j-1] 1当s1[i-1] ! s2[j-1]说明当前这两个字符不能同时入选那答案要么来自s1去掉当前字符后的最优解要么来自s2去掉当前字符后的最优解取较大值即dp[i][j] max(dp[i-1][j], dp[i][j-1])。为什么最后一个字符相同的时候可以直接1因为这两个字符相等把它们放在公共子序列的末尾不会跟前面的选择冲突而且任何“公共子序列”最多只能包含每个字符串的一个末尾字符所以直接把当前字符接上是最优的。这个“贪心”在 LCS 里是安全的但注意这个安全成立的前提是前面的子序列已经是最优。3.3 填表过程可视化为什么必须按行遍历用s1 abcde和s2 ace来手动填一遍表。两个字符串的长度分别是 5 和 3所以 dp 表是 6 行 4 列多出的行和列是空串的 0。初始第一行和第一列全是 0。然后按行从左到右填。这里我直接给一个关键结论dp 表里每个格子的值只依赖它左上角、正上方、正左方这三个格子所以在循环时只要保证先行后列、从上到下从左到右地填充每个格子的前置依赖一定已经计算过了。 a c e 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 e 0 1 2 3表格右下角的3就是最长公共子序列的长度。你从右下角回溯如果s1[i-1] s2[j-1]这个字符就属于 LCS 的一部分向左上移动如果不相等看dp[i-1][j]和dp[i][j-1]谁大就往哪边移动。这样就能还原出ace。再举一个不对称的例子s1 abcd,s2 bc。公共子序列是bc长度 2。你填表后会观察到dp的值在首行首列之外是“非递减”的这很符合直觉——字符越多公共子序列最长只会更长或持平不可能变短。3.4 时间复杂度与空间复杂度分析填一张(m1) × (n1)的表每个格子只做常数次比较所以时间复杂度是 O(mn)空间复杂度也是 O(mn)。对于字符串长度在几千以内的场景这个空间开销完全可接受。但如果两个文本各有一万行代码dp 表的规模就是一亿个格子——几百 MB 的内存直接爆掉。这时候就需要空间优化方案我在第 5 章节会专门讲。提示面试中问到“能不能进一步优化空间复杂度”是非常常见的追问别只背 O(mn) 的解法请把滚动数组的方法也掌握扎实。4. 代码实现从二维 DP 到一维滚动数组优化4.1 标准的二维 DP 实现先用最标准的二维数组实现突出一个“稳”字。语言我用的是 Go这套逻辑切换成 Python、C、Java 都很简单func longestCommonSubsequence(s1, s2 string) int { m, n : len(s1), len(s2) dp : make([][]int, m1) for i : range dp { dp[i] make([]int, n1) } for i : 1; i m; i { for j : 1; j n; j { if s1[i-1] s2[j-1] { dp[i][j] dp[i-1][j-1] 1 } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]) } } } return dp[m][n] } func max(a, b int) int { if a b { return a } return b }这段代码有几个容易出错的点循环从1开始到m/n结束因为第 0 行第 0 列代表空串取字符时用的是s1[i-1]而不是s1[i]因为i代表长度很多人 debug 半天找不到越界或者结果差 1问题就出在这里函数内部没有对空字符串做特殊处理但依赖dp表初始化为 0 的逻辑自动覆盖了空串边界。4.2 空间优化为什么可以只用两行仔细观察状态转移方程dp[i][j]只和dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]有关。换句话说当前行的计算只需要上一行的数据和当前行左侧已经算出的数据更早的行在算完之后就再也不会被用到了。所以可以只保留两行数组算完一行就丢弃上一行。这种技巧叫“滚动数组”。如果题目只需要长度、不需要还原具体子序列这是最常用的优化方案func longestCommonSubsequenceOptimized(s1, s2 string) int { m, n : len(s1), len(s2) prev : make([]int, n1) cur : make([]int, n1) for i : 1; i m; i { for j : 1; j n; j { if s1[i-1] s2[j-1] { cur[j] prev[j-1] 1 } else { cur[j] max(prev[j], cur[j-1]) } } prev, cur cur, prev // 注意交换后cur 里还是旧数据要在每轮循环里覆盖 } return prev[n] }这里有个坑每次内层循环结束后交换prev和cur下一轮开始的时候cur里残留着上一轮的数据如果哪一格没被赋值就会出问题。但好在外层循环每一轮都会把cur的所有下标从 1 到 n 重新赋值一遍所以逻辑上是安全的。唯一要留意的是cur[0]始终是 0这个值在循环里不会变符合边界条件。4.3 继续优化到一维数组难点在于左上角的值既然只用上一行和当前行那是不是可以直接用一维数组只保留一行一边遍历一边覆盖可以的但有一个细节特别容易翻车。一维数组dp[j]在更新时代表的是“当前行第 j 列”的值。当我们计算dp[j]时需要三个值dp[j-1]当前行左侧的旧值不对注意dp[j-1]在 j 循环里已经先被更新过了所以它代表的是当前行第 j-1 列的新值也就是dp[i][j-1]这个是正的dp[j]还没被当前行覆盖它还是上一行第 j 列的值也就是dp[i-1][j]也是正的dp[i-1][j-1]也就是上一行的j-1位置这个值在dp[j-1]被覆盖的时候就已经丢了。所以关键问题来了当s1[i-1] s2[j-1]时要使用dp[i-1][j-1]但一维数组里这个值已经被覆盖了。解决办法是在每次内层循环里用一个临时变量保存“上一行的 j-1 格”func longestCommonSubsequenceOneDim(s1, s2 string) int { n : len(s2) dp : make([]int, n1) for i : 1; i len(s1); i { prevDiagonal : 0 // 初始为 dp[j-1] 的上一行值即 dp[i-1][0]是 0 for j : 1; j n; j { temp : dp[j] // 保存当前格子的旧值这是下一轮循环的 prevDiagonal if s1[i-1] s2[j-1] { dp[j] prevDiagonal 1 } else { dp[j] max(dp[j], dp[j-1]) } prevDiagonal temp } } return dp[n] }这段代码是面试高频考点。你不需要在面试时背它只要理解了prevDiagonal保存的是“上一行 j-1 的值”就永远不会写错。它相当于把二维表格压成了一条线用“在前一个格子被覆盖之前先把它存起来”的方式保住了那个唯一的必须用到的旧值。4.4 不只求长度如何还原最长公共子序列本身很多时候我们不仅需要长度还需要知道 LCS 到底是哪一个字符串。比如你要在 diff 工具里展示两个版本共同保留的部分就必须还原出具体的子序列。还原过程要用到完整的 dp 表因为你需要在整个表上回溯。算法思路如下从dp[m][n]开始往回走如果s1[i-1] s2[j-1]说明这个字符入选把它记录下来然后i--, j--如果不等那就对比dp[i-1][j]和dp[i][j-1]谁大往谁那边走如果相等任选一边即可这说明存在多个不同的 LCS方向选择会影响最终还原出哪一个。用s1 abcde、s2 ace来走一遍走到dp[5][3]3先看e e入选e到dp[4][2]d ! cdp[4][2]和dp[3][2]都是 2任选一边最终能还原出ace。如果把s1换成aebdc你会发现aec和abc都是合法的 LCS长度一样内容不同。这一点在工程上很重要——两个文本的 diff 结果不唯一展示了“哪一种共同保留部分”取决于你回溯方向的优先级。5. 复杂度进阶位运算并行化与典型实际应用场景5.1 当字符串超长时m 远大于 n 的处理策略前面提到一维数组可以把空间从 O(mn) 降到 O(n)但那是在 m 和 n 差不多大的时候。如果其中一个字符串特别长比如一个 100 万字的长文本和一个 100 字的短短语找 LCS那我们可以把短的那条串作为 n长的那条作为 m空间只开 n 的长度。代码里只需要在最初比较两个字符串的长度如果len(s1) len(s2)就交换保证外层循环是长串、内层循环是短串这样一维 DP 的内层数组永远是 O(短串长度)。这种“内层选短的”的策略在工程里很常用不止 LCS像 Edit Distance 这类带网格的 DP 问题同样适用。5.2 位运算并行化一种比较少见的加速技巧有一种针对小字符集的高性能优化把字符集映射成位掩码然后用位运算同时处理 64 个位置的匹配情况。具体做法是先对每个字符记录它在短串中出现的位置集合用一个 64 位的整数mask[c]标注某个字符出现在短串的哪些位置然后遍历长串用一段优化的位操作更新状态。这个算法能把复杂度从 O(mn) 压到 O(m × n/64)原理是每次迭代同时处理了一个 64 位机器字里多个位置的“匹配—传播”过程。实际工程里像基因序列比对这种对速度要求极高的场景会用到这类并行化技巧。对于普通业务场景一维滚动数组已经足够不必过早追求这种在位运算层面才有的加速。真要深入推荐阅读专门讲“Bitap 算法”和“BLAST 序列比对”的资料LCS 的位运算版本是它们的近亲。5.3 应用场景一代码 diff 与版本控制git diff的核心算法虽然做了很多工程化变形但其根基就是 LCS。两个文件版本分别视为一个字符串序列按行切分求出它们的公共子序列后不在公共子序列里的行就是新增或删除的行。因为 LCS 不唯一diff 工具会通过权重调整来让输出更“人类友好”——比如尽量让删除和新增成对出现避免大面积的行重新排序。有一个很常见的误区很多人觉得 diff 需要的是“最长公共子串”因为看到 diff 输出里大片的连续相同行。实际上连续相同的行是公共子串但它只是公共子序列的特例按行比对时连续的行在序列意义上也是连续的所以两者表现一致。但真正决定 diff 正确性的还是 LCS 逻辑否则一次插入一个空行就会导致整个文件被判定为全部重写。5.4 应用场景二文本相似度与查重把两个文本的 LCS 长度除以某种归一化分母通常是两个文本中较长者的长度可以得到一个相似度指标。比如在两段代码的抄袭检测场景中系统会先做 token 化或按行切分再算 LCS相似度超过阈值就标记。这里要注意LCS 相似度对“文本内字符顺序被整体打乱”的情况完全无感——你把两个段落调换顺序LCS 可能会发生剧烈变化。所以工程上通常不会只用 LCS 一个指标判断重复而是结合 N-gram 重叠、编辑距离等一起做。我在实际项目中见过有人只拿 LCS 做查重结果两份结构不同但完全复制的文档没被查出来因为 LCS 对“被插入大量干扰字符”的敏感度不高。这个坑要提前规避。5.5 应用场景三生物信息学中的序列比对DNA 序列本质就是A/T/C/G组成的超长字符串。两个基因序列的公共子序列长度在生物信息学里对应着“同源片段”的长度估计。真实的序列比对算法如 Needleman-Wunsch其实是在 LCS 基础上加入了替换惩罚和空位惩罚的加权版本相当于更一般化的全局比对问题。这类场景中字符串长度可以达到数百万量级DP 的 O(mn) 复杂度就撑不住了所以工业界会使用启发式算法如 BLAST先快速定位高相似度的种子片段再在局部做精确比对。这给我们一个启发算法题里的标准解法是“精确且正确”的范式但真实系统往往需要在正确性和性能之间做取舍。6. 工程实践如何用 LCS 做一个简易的文本差异化工具6.1 需求拆解不只是算长度还要输出“差异块”纯算 LCS 长度其实没多少工程价值真正有用的是输出哪些行是公共的、哪些行是新增的、哪些行是删除的。我来设计一个迷你 diff 工具。输入是两个字符串按\n切分成行数组然后用二维 DP 求出 LCS 的行索引映射回溯时输出三种标记common公共行、deleted只在旧文本中出现的行、added只在新增文本中出现的行。这里的关键点在于我们要的不是“公共子序列的长度”而是“哪些行在公共子序列里”。所以 DP 表必须完整保留不能使用空间优化的一维数组——因为回溯阶段需要任意访问历史状态。6.2 具体实现步骤先写一个生成 DP 表的函数func buildDPTable(lines1, lines2 []string) [][]int { m, n : len(lines1), len(lines2) dp : make([][]int, m1) for i : range dp { dp[i] make([]int, n1) } for i : 1; i m; i { for j : 1; j n; j { if lines1[i-1] lines2[j-1] { dp[i][j] dp[i-1][j-1] 1 } else { if dp[i-1][j] dp[i][j-1] { dp[i][j] dp[i-1][j] } else { dp[i][j] dp[i][j-1] } } } } return dp }注意在回溯时可能会遇到dp[i-1][j] dp[i][j-1]的情况此时我选择优先往上走视为deleted这样 diff 的输出会更稳定不会因为方向瞎跳导致结果时对时错。然后是回溯函数type DiffLine struct { Kind string // common / deleted / added Text string } func backtrack(lines1, lines2 []string, dp [][]int) []DiffLine { i, j : len(lines1), len(lines2) var result []DiffLine for i 0 j 0 { if lines1[i-1] lines2[j-1] { result append(result, DiffLine{common, lines1[i-1]}) i-- j-- } else if dp[i-1][j] dp[i][j-1] { result append(result, DiffLine{deleted, lines1[i-1]}) i-- } else { result append(result, DiffLine{added, lines2[j-1]}) j-- } } for i 0 { result append(result, DiffLine{deleted, lines1[i-1]}) i-- } for j 0 { result append(result, DiffLine{added, lines2[j-1]}) j-- } // 因为是从尾往头回溯的最后要反转 reverse(result) return result }这个实现和git diff的输出方向不太一样它是从末尾往前收集、最后反转。核心逻辑就是如果当前两行相等归为公共行如果不相等看 dp 表决定是“删除旧行的内容”还是“加入新行的内容”。6.3 实测一下假设我们有两个版本旧版本function hello() { console.log(hello); }新版本function hello() { const msg hello; console.log(msg); }按行切分后console.log(hello);是公共的其他行会有增删。你运行上面代码后会得到类似下面的输出common function hello() { deleted console.log(hello); added const msg hello; added console.log(msg); common }注意这里的顺序看起来有点怪console.log(hello);被标记删除console.log(msg);被标记新增虽然它们语义上很像但 LCS 是按“完全相等”来匹配行的。如果你想让 diff 更聪明识别出hello变成了msg那是语义 diff 的范畴需要更高层次的 AST 解析LCS 本身不负责这件事。6.4 性能与内存什么时候需要分块处理上面这个简易 diff 是 O(mn) 时间和 O(mn) 空间的。如果两个文件各有 5000 行dp 表就是 2500 万个格子内存大约 200 MB每个 int 8 字节。这在真实工程里就有点吃不消了。实用的降内存方案是分块先用哈希找到两边完全相同的“锚点行”通常是空行、大括号行、独有特征行把大文件切成若干小块每个小块内部再跑完整 DP。这个思路是 Myers diff 算法的前置近似也是很多真实 diff 工具的优化方向之一。如果你只是写个小工具自己用可以先不优化如果要用到生产环境分块几乎是必须的。6.5 工程实现的常见误区第一不要拿字符串作为 dp 表里比较的最小单位除非你明确知道行为粒度。如果按字符比较大文件 diff 会慢到无法使用。按行比较每一行是一个原子然后行内部再做二次 diff比如列级 diff这种分层策略是文本比对工具的标准做法。第二回溯方向会影响输出稳定性。我见过同事写的 diff 工具在相同输入下来回变化就是因为 dp 值相等时选择的回溯方向不稳定。解决办法是固定一个优先级比如“优先删旧行”——这样输出永远确定。第三注意换行符差异。Windows 的\r\n和 Linux 的\n会让每一行看起来不一样导致 diff 结果全是增删。切分前先把\r去掉这是基础中的基础。7. 面试避坑指南状态压缩的隐藏细节与相似题目串联7.1 面试官真正想考察什么LCS 在面试里高频出现不只是因为它解法经典更因为它能考察多个维度边界处理、空间优化意识、回溯还原能力、以及迁移能力变体题能不能套用同一套 DP 框架。很多候选人能把二维 DP 默写出来但一问“为什么转移方程里相等时用dp[i-1][j-1] 1而不是dp[i-1][j] 1”“不相等时为什么不是max(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])”“一维数组优化时那个被覆盖的左上角值怎么保存”这三个问题能答上来的人才算真正理解了这道题而不是背了个模板。第一个问题的答案前面已经说过第二个问题值得多说一句dp[i-1][j-1]其实被dp[i-1][j]和dp[i][j-1]间接包含了——因为 dp 值非递减dp[i-1][j]一定不小于dp[i-1][j-1]dp[i][j-1]同理所以那个三项的 max 等价于两项的 max。面试时能指出这一点是加分项。7.2 相似题对比LCS、编辑距离、最长递增子序列我强烈建议把这三道题放在一起对比学习因为它们共享同一个 DP 骨架只是转移方程的细节不同LCS相等时dp[i-1][j-1] 1不等时取max(dp[i-1][j], dp[i][j-1])编辑距离Edit Distancedp[i][j]表示把s1[0..i-1]变成s2[0..j-1]的最少操作数转移时考虑增、删、改三操作取三者最小值最长递增子序列LIS一维 DPdp[i]表示以第 i 个元素结尾的最长递增子序列长度转移时向前扫描所有j i且nums[j] nums[i]或使用二分优化到 O(n log n)。把它们放在一起看你会发现自己掌握了“动态规划自底向上的通用填表框架”定义状态、找转移、定边界。剩下的就是在具体问题上做出不同的选择判断。7.3 关于“多个 LCS 输出”的经典陷阱如果题目问“请输出所有可能的最长公共子序列”难度瞬间上升。因为回溯时遇到dp[i-1][j] dp[i][j-1] dp[i][j]的岔路两条路都要走这就从单路径回溯变成了 DFS 枚举最坏情况下输出量本身就是指数级的。面试中建议先和面试官确认输出数量限制同时设计去重策略比如用哈希集合存中间结果避免重复递归。去重的常用方法是“按位置去重”在 DFS 回溯时记录当前走到(i, j)以及已经拼出的后缀结果如果同一(i, j)曾经用相同的后缀访问过就剪枝。这个优化可以把大量重复分支剪掉但对极端构造的场景仍然会爆炸因为合法答案数量本身是指数级的。7.4 刷题节奏建议如果 LCS 是你接触的第一个动态规划题目我的建议是这样的学习路径先手写暴力递归版本体会指数爆炸加一个 memo 数组改成自顶向下记忆化搜索改写成自底向上的二维 DP改写成滚动数组一维版本最后实现回溯还原子序列。每一层改动都亲手编译、运行、测试。很多人在第二步就跳过直接背第四步结果面试时被问到“为什么这么写”就卡住了。就我个人的体会这五步走一遍比刷十道 DP 题效率都高因为你在过程中反复体验的是同一种计算模式的自洽和边界约束而不是孤立地背结论。8. 实操心得与下一步扩展方向8.1 我踩过的几个坑第一dp 表初始化陷阱。二维切片在 Go 里必须逐行make我一开始想当然地以为二维数组可以一次性make([][]int, m1, n1)结果跑起来直接 panic——这是切片嵌套的结构不是真正的二维数组。这在 C/Java 里不常见但在 Go 和 Python二维列表里特别容易踩。第二字符相等时直接1的“贪心直觉”。我曾经在相等的情况下写成dp[i][j] dp[i-1][j] 1因为觉得“既然当前字符相等那就在上一行的基础上加 1 就行了”——这是错的。你要加上去的那个字符必须接在s1和s2都去掉当前字符后的最优序列后面也就是dp[i-1][j-1] 1。写成dp[i-1][j]意味着你跳过了s2的当前字符但你又用了这个字符逻辑上自相矛盾。第三回溯时忘了把结果反转。回溯是从表尾走向表头收集的字符天然是倒序。如果你忘了reverse会输出一个完全反向的 LCS。签名是dp[m][n]不是dp[len(s1)][len(s2)]的这种低级错误我就不多说了写代码时把长度变量命名为m, n并且严格区分“长度”和“下标”是减少这种错误最有效的办法。8.2 后续可以这样扩展如果你想把 LCS 吃透并且让它发挥更大价值我建议往这几个方向延伸Myers diff 算法这是git diff真正使用的核心算法它的思路是用编辑脚本的路径搜索代替 DP 填表在“两个文件大部分相同”时时间复杂度接近 O(ND)远快于 O(mn)。理解 Myers 算法之后再看 LCS会有一种“原来 DP 只是其中一种实现”的豁然感。加权序列比对在 LCS 基础上引入替换、插入、删除的不同代价就变成了序列比对里的经典全局比对问题。生物信息学里的 Needleman-Wunsch 算法就是这个版图里的一员搞懂它以后你会把“字符串相同”的思维升级成“字符串相似”的思维。多序列比对两个序列的 LCS 很容易但三个及以上序列找公共子序列就是 NP-hard 了工业界用的都是启发式算法。从这个点出发你能理解“为什么很多真实的复杂问题不能只靠一道算法题解决”。8.3 最后说一句大实话动态规划这个板块很多人是“背着背着就过了”但 LCS 这道题特别适合做理解 DP 的锚点因为它简单到状态定义一句话就能说清又深刻到能延展出 diff、比对、并行优化这些工程话题。我见过不少同事在项目里遇到文本比对需求时第一反应是去找第三方库完全没有意识到自己可以在一晚上写出一个可用的精简版——实际上掌握了 LCS 的 DP 表加回溯就能覆盖一大部分真实需求了。如果你正在准备面试建议把 LCS 的“五步进阶法”亲手走一遍如果你是在做工程建议直接把我前面那个迷你 diff 的代码跑一下然后加上分块优化你会对版本控制工具底层多一份实实在在的理解。算法题和工程实现之间的鸿沟往往就是从“我理解了”到“我能写出来还能讲清楚为什么这么写”之间拉开的。