1. 从一道面试题说起：最长公共子序列到底在解决什么问题

第一次接触最长公共子序列（Longest Common Subsequence，简称LCS）是在准备一场技术面试的时候。面试官在白板上写了两行字符串，问我：“这两个字符串最长的公共子序列是什么？长度是多少？”我当时脑子里第一反应是“最长公共子串”，差点脱口而出。后来才意识到，子序列和子串完全是两码事——子串要求连续，子序列不要求连续，但顺序不能乱。这个区别看似微小，却直接决定了问题从“滑动窗口能搞定”变成了“必须上动态规划”。

LCS这个问题，说白了就是：给定两个序列，找出它们共同拥有的、保持相对顺序但不要求连续的最长子序列。比如序列A是“ABCBDAB”，序列B是“BDCABA”，它们的LCS是“BCBA”或者“BDAB”，长度都是4。注意这里可能有多个解，但长度是唯一的。这个问题在计算机科学里的地位非常高，它是动态规划算法的经典教学案例，也是很多实际系统的核心组件——比如代码版本控制里的diff算法、生物信息学里的DNA序列比对、自然语言处理里的文本相似度计算，底层都离不开LCS或者它的变体。

为什么值得花时间深挖这个问题？因为LCS是理解动态规划思想的最佳入口之一。它不像背包问题那样有那么多变体让人眼花缭乱，也不像图论算法那样需要额外的数据结构基础。它就是两个序列、一个二维表格、一个递推公式，干净利落。但正是这种简洁，让它成为了检验一个人是否真正理解动态规划的试金石。我见过太多人背下了递推公式却说不清楚为什么这样递推，也见过有人在面试时写出了O(mn)的解法却不知道空间可以优化到O(min(m,n))。这篇文章就是想把LCS从里到外拆干净，让不同基础的人都能真正掌握它。

2. 动态规划解LCS的核心思路拆解

2.1 为什么贪心和分治在这里不好使

遇到“最长”“最优”这类字眼，很多人第一反应是贪心。但LCS问题不满足贪心选择性质。举个例子，A=“ABCBDAB”，B=“BDCABA”。如果贪心地从前往后匹配，第一个共同字符是B，然后继续往后找，可能会得到“BCBA”或者“BDAB”，看起来还行。但换一组序列，比如A=“ABCD”，B=“ACBD”，贪心匹配第一个共同字符A，然后找下一个共同字符，可能得到“ABD”或者“ACD”，长度是3。但实际上LCS是“ABD”或“ACD”，长度也是3，这个例子不够明显。再换一个：A=“AGGTAB”，B=“GXTXAYB”。贪心如果先匹配A，后面可能只能匹配到B，得到“AB”，长度2。但实际LCS是“GTAB”，长度4。贪心在这里彻底失效，因为它做了局部最优的选择，却牺牲了全局最优。

分治法呢？把两个序列各切一半，分别求LCS再合并？问题在于LCS的最优解不一定由子问题的最优解组合而成。两个序列的LCS可能跨越切分点，导致子问题的解无法直接拼接。分治适合子问题独立的情况，而LCS的子问题之间存在重叠和依赖，所以分治也不合适。

动态规划之所以适合，是因为LCS问题具有两个关键性质：最优子结构和重叠子问题。最优子结构意味着原问题的解可以由子问题的解推导出来；重叠子问题意味着不同的子问题会重复出现，可以用表格缓存结果避免重复计算。这两点一结合，动态规划就是最自然的解法。

2.2 状态定义与递推关系的推导过程

动态规划的第一步永远是定义状态。对于LCS，我们有两个序列，所以状态自然就是二维的。定义dp[i][j]表示序列A的前i个字符（即A[0..i-1]）和序列B的前j个字符（即B[0..j-1]）的最长公共子序列长度。注意这里的索引是从1开始的，dp[0][j]和dp[i][0]都表示其中一个序列为空的情况，此时LCS长度显然是0。

接下来推导递推关系。考虑A的第i个字符A[i-1]和B的第j个字符B[j-1]：

• 如果A[i-1] == B[j-1]，那么这两个字符可以成为LCS的一部分。既然它们相等，把它们加到之前的最优解后面一定不会变差。所以dp[i][j] = dp[i-1][j-1] + 1。
• 如果A[i-1] != B[j-1]，那么这两个字符不可能同时出现在LCS的末尾。LCS要么来自A的前i-1个字符和B的前j个字符，要么来自A的前i个字符和B的前j-1个字符。取两者中较大的那个：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

这个递推关系看起来简单，但背后的逻辑需要仔细体会。为什么相等的时候直接加1就行？因为如果两个字符相等，把它们匹配上一定不会比不匹配更差。这个可以用反证法证明：假设最优解没有匹配这两个相等的字符，那么我们可以把它们加进去，得到一个更长的公共子序列，矛盾。所以相等时直接匹配是最优的。

为什么不等的时候只看左边和上边？因为dp[i][j]的所有可能来源只有三种：dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。当A[i-1] != B[j-1]时，dp[i-1][j-1]不可能比dp[i-1][j]或dp[i][j-1]更大，因为dp[i-1][j] >= dp[i-1][j-1]（多考虑了一个字符B[j-1]，LCS长度不会减少），同理dp[i][j-1] >= dp[i-1][j-1]。所以只需要比较后两者。

2.3 二维DP表格的填充逻辑与可视化理解

把递推关系画成表格，理解起来会直观很多。以A=“ABCBDAB”和B=“BDCABA”为例，构造一个8行7列的表格（行对应A的长度0到7，列对应B的长度0到6）。第一行和第一列全部填0，因为空序列和任何序列的LCS都是0。

然后逐行逐列填充。比如dp[1][1]对应A[0]=‘A’和B[0]=‘B’，不相等，取max(dp[0][1], dp[1][0]) = max(0,0) = 0。dp[1][2]对应A[0]=‘A’和B[1]=‘D’，不相等，取max(dp[0][2], dp[1][1]) = max(0,0) = 0。继续填下去，当遇到相等字符时，比如dp[2][1]对应A[1]=‘B’和B[0]=‘B’，相等，dp[2][1] = dp[1][0] + 1 = 1。

整个表格填完后，右下角dp[7][6]就是最终答案。这个表格的填充过程有一个很实用的可视化技巧：把相等字符的位置标记出来，然后从右下角往左上角回溯，就能找到具体的LCS。回溯的规则是：如果A[i-1] == B[j-1]，那么这个字符属于LCS，同时i和j都减1；否则比较dp[i-1][j]和dp[i][j-1]，往较大的方向移动。这样就能还原出一个具体的LCS。

注意：回溯时如果dp[i-1][j]和dp[i][j-1]相等，往哪个方向走都可以，会得到不同的LCS，但长度相同。这也是LCS可能不唯一的原因。

3. 从伪代码到可运行实现：完整实操过程

3.1 基础二维DP版本的代码实现与逐行解析

先给出最直观的二维DP实现，用Python写：

def lcs_length(A, B): m, n = len(A), len(B) # 创建(m+1) x (n+1)的二维数组，初始化为0 dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): 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]) return dp[m][n]

这段代码的时间复杂度是O(mn)，空间复杂度也是O(mn)。逐行来看：第一行创建二维数组，Python里用列表推导式比[[0](n+1)](m+1)安全，因为后者会导致所有行引用同一个列表对象，修改一行会影响所有行。这是一个非常经典的Python坑，我当年就踩过，调试了半天才发现问题。

外层循环遍历A的每个字符，内层循环遍历B的每个字符。当字符相等时，取左上角的值加1；不等时，取左边和上边的最大值。最后返回dp[m][n]。

如果要还原具体的LCS而不只是长度，需要额外做回溯：

def lcs_string(A, B): m, n = len(A), len(B) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): 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]) # 回溯构造LCS result = [] i, j = m, n while i > 0 and j > 0: if A[i-1] == B[j-1]: result.append(A[i-1]) i -= 1 j -= 1 elif dp[i-1][j] >= dp[i][j-1]: i -= 1 else: j -= 1 return ''.join(reversed(result))

回溯部分从右下角开始，遇到相等字符就收集并往左上走，否则往数值较大的方向走。最后反转结果就是LCS。这个实现的时间复杂度仍然是O(mn)，因为回溯最多走m+n步。

3.2 空间优化：滚动数组把O(mn)降到O(min(m,n))

二维DP的空间复杂度是O(mn)，当两个序列都很长时，内存消耗会很大。比如两个长度都是10000的序列，二维数组需要1亿个整数，在Python里每个整数对象占28字节，总共约2.8GB，显然不可接受。但实际上我们只需要最终长度，不需要完整的表格，所以可以优化空间。

观察递推关系：dp[i][j]只依赖于dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]。也就是说，计算第i行时只需要第i-1行的数据。所以可以用两个一维数组滚动更新，空间降到O(n)。进一步，如果让较短的序列作为列，空间可以降到O(min(m,n))。

def lcs_length_optimized(A, B): # 让B成为较短的序列，减少空间 if len(A) < len(B): A, B = B, A m, n = len(A), len(B) prev = [0] * (n + 1) curr = [0] * (n + 1) for i in range(1, m + 1): for j in range(1, n + 1): if A[i-1] == B[j-1]: curr[j] = prev[j-1] + 1 else: curr[j] = max(prev[j], curr[j-1]) prev, curr = curr, prev # 注意：交换后curr还是旧数据，但下一轮会覆盖，不影响 return prev[n]

这里有一个细节需要注意：交换prev和curr之后，curr里还保留着上一轮的数据，但下一轮内层循环会从j=1开始逐个覆盖，所以不会影响结果。不过为了代码清晰，也可以在每轮开始前把curr清零，但那样会多一次O(n)的操作，没必要。

实操心得：滚动数组的写法容易在索引上出错，建议先用小规模数据对比二维版本和优化版本的结果，确认一致后再用于大规模数据。我一般会写一个随机测试函数，生成100组随机字符串，对比两个版本的输出。

3.3 参数选择与边界条件处理

在实际实现中，有几个边界条件需要特别注意：

• 空序列：如果A或B为空，LCS长度为0。二维DP中dp[0][j]和dp[i][0]都是0，自动处理了这种情况。
• 单字符序列：如果A和B都只有一个字符，相等则返回1，不等返回0。递推关系也能正确处理。
• 完全相同：如果A和B完全相同，LCS就是A本身，长度为len(A)。此时dp[i][j] = i（当i=j时），递推关系会一路加1。
• 完全不相同：如果A和B没有任何共同字符，LCS长度为0。此时所有dp[i][j]都是0。

对于回溯构造LCS，边界条件是i>0且j>0。当其中一个减到0时循环结束，此时result中收集的字符就是LCS。

还有一个容易忽略的点：Python中字符串索引是从0开始的，而dp数组的索引是从1开始的，所以访问A[i-1]和B[j-1]时要注意减1。这个off-by-one错误在面试白板上写代码时特别容易犯，建议写完后用一个小例子手动验证一遍。

4. 常见问题与排查技巧实录

4.1 递推方向写反导致结果错误

这是新手最容易犯的错误之一。有人会把dp[i][j] = dp[i-1][j-1] + 1写成dp[i][j] = dp[i+1][j+1] + 1，或者把max(dp[i-1][j], dp[i][j-1])写成max(dp[i+1][j], dp[i][j+1])。方向写反后，代码可能不报错，但结果完全不对。

排查方法：用最简单的例子手动模拟。比如A=“A”，B=“A”，正确答案是1。如果代码返回0或者报索引越界，说明方向有问题。再比如A=“AB”，B=“AB”，正确答案是2。如果返回1，说明递推方向可能反了。

4.2 空间优化版本中prev和curr的更新时机

滚动数组版本中，prev和curr的交换时机很关键。如果在内层循环之前交换，会导致prev和curr指向错误的数据。正确的做法是在内层循环结束后交换，这样下一轮外层循环开始时，prev指向的是上一行的数据，curr指向的是上上行的数据（会被覆盖）。

还有一个更隐蔽的问题：如果在内层循环中同时读写prev和curr，要注意curr[j-1]是当前行已经计算过的值，而prev[j]是上一行的值。这两个值在递推中都会用到，不能混淆。

4.3 回溯时路径选择导致LCS不唯一

前面提到过，当dp[i-1][j] == dp[i][j-1]时，往哪个方向走都可以，会得到不同的LCS。这不是bug，而是LCS问题本身的特性。如果业务场景要求返回字典序最小的LCS，需要在回溯时加额外的判断逻辑。比如当两个方向数值相等时，优先往能产生更小字符的方向走。

4.4 大规模数据下的性能瓶颈与优化思路

O(mn)的时间复杂度在序列长度达到万级别时就会明显变慢。比如两个长度10000的序列，需要1亿次操作，在Python里可能需要几十秒。优化思路有几个：

• 使用更快的语言实现，比如C++或Rust，同样的算法能快几十倍。
• 利用位运算并行化，比如Hunt-Szymanski算法在特定条件下能降到O((r+n)logn)，其中r是匹配字符对的数量。
• 使用分块策略，把大序列切成小块分别计算，但要注意块边界的处理。
• 如果只需要长度不需要具体序列，可以用一些近似算法或者启发式方法，但会牺牲精确性。

注意：Hunt-Szymanski算法虽然理论上更快，但实现复杂度高，且在实际数据上不一定比优化过的DP快，因为它的常数因子较大。选择算法时要根据实际数据特征来决定。

4.5 常见问题速查表

5. LCS在实际场景中的应用与变体

5.1 代码版本控制中的diff算法

用过Git的人都知道git diff能显示两个版本之间的差异。这个功能的核心就是LCS。具体来说，Git把两个版本的每一行当作一个元素，然后求两个行序列的LCS。LCS中的行就是没有变化的行，不在LCS中的行就是新增或删除的行。通过标记这些行，就能生成diff输出。

这个应用场景对LCS的实现有特殊要求：需要快速处理大文件，所以Git用了Myers差分算法，它本质上是对LCS问题的一种优化，时间复杂度在最好情况下是O(ND)，其中N是总行数，D是差异行数。当两个版本差异很小时，Myers算法比标准DP快得多。

5.2 生物信息学中的DNA序列比对

DNA序列由A、T、C、G四种碱基组成，比较两个DNA序列的相似性是生物信息学的基本任务。LCS可以用来衡量两个序列的相似程度，但实际中更常用的是带权重的编辑距离（如Needleman-Wunsch算法），它允许插入、删除和替换操作，并给不同操作赋予不同的代价。LCS可以看作是编辑距离的一个特例，只允许插入和删除，不允许替换。

在DNA序列比对中，序列长度可能达到百万级别，所以标准O(mn)的DP完全不可行。实际使用的是BLAST等启发式算法，先找到短的精确匹配片段（种子），再向两边扩展。这些算法的底层思想仍然与LCS相关。

5.3 文本相似度计算与抄袭检测

在自然语言处理中，判断两段文本的相似度是一个常见需求。一种简单的方法是把文本分词后求LCS，LCS长度除以较长文本的长度就是相似度的一个粗略估计。当然实际中会用更复杂的模型，比如TF-IDF、词向量、BERT等，但LCS作为一个基础方法，在快速原型和简单场景中仍然有用。

抄袭检测系统也常用LCS的变体。比如把两篇论文的句子序列作为输入，求最长公共子序列，如果LCS长度超过某个阈值，就认为存在抄袭嫌疑。这种方法对语序调整的抄袭有一定检测能力，但对同义词替换的抄袭效果有限。

5.4 其他变体：最长公共子串、最长递增子序列

LCS有几个容易混淆的亲戚：

• 最长公共子串：要求连续，可以用后缀自动机或后缀数组在O(n)时间内解决，也可以用DP但递推关系不同（不等时直接置0）。
• 最长递增子序列：只有一个序列，要求递增，可以用耐心排序在O(nlogn)时间内解决。
• 最长公共递增子序列：结合了LCS和LIS，需要在LCS的基础上加递增约束，DP状态需要额外记录末尾元素。

这些变体在面试中经常被拿来对比考察，理解它们之间的区别和联系，能帮助你在遇到新问题时快速定位到合适的算法。

6. 我个人在实际操作中的几点体会

LCS这个问题我前前后后实现过不下十遍，每次都有新的收获。最开始是死记硬背递推公式，后来慢慢理解了背后的最优子结构，再后来开始关注空间优化和实际应用。有几个体会特别深：

第一，不要小看边界条件。空序列、单字符、完全相同、完全不相同，这四种情况覆盖了大部分边界bug。每次写完代码，先用这四种情况测试一遍，能省下大量调试时间。

第二，空间优化不是必须的，但值得掌握。在面试中写出二维DP已经及格，能写出滚动数组版本是加分项。在实际工程中，如果序列长度可能很大，空间优化就是必须的。

第三，理解LCS的局限性。LCS只考虑字符是否相等，不考虑语义相似性。在实际应用中，往往需要结合其他技术。比如文本相似度计算中，先做同义词替换再求LCS，效果会好很多。

第四，多动手写。看十遍不如写一遍。我建议每个学习动态规划的人都亲手实现一遍LCS，包括二维版本、空间优化版本和回溯构造版本。写完之后再用随机数据测试，确保理解到位。

最后分享一个小技巧：如果面试中被问到LCS，可以先问清楚是求长度还是求具体序列，是要求一个解还是所有解，序列长度大概是多少。这些信息会直接影响你的实现选择。问清楚再动手，比闷头写代码然后发现方向错了要好得多。