1. 从一道15分题说起最长公共子序列到底在考什么如果你正在刷算法训练营的题目看到“最长公共子序列长度”这几个字大概率第一反应是“这题我见过”然后脑子里蹦出两个字符串、一个二维表格、几行状态转移方程。但真到上手写的时候很多人会在初始化、遍历顺序、边界处理上卡住最后提交上去不是答案偏小就是数组越界。这道题在训练营里只值15分看起来不起眼但它几乎是所有动态规划入门者绕不开的一道坎也是面试中考察DP思维的高频题。先把概念说清楚。最长公共子序列Longest Common Subsequence简称LCS指的是给定两个序列找出它们共有的、保持原有相对顺序但不要求连续的子序列中长度最大的那个。注意这里有两个关键词——“不要求连续”和“保持相对顺序”。很多人第一次会把“子序列”和“子串”搞混。子串要求在原序列里是连续的一段而子序列只要求顺序一致中间可以跳过任意字符。举个例子字符串abcde和ace它们的公共子序列可以是ace长度是3但公共子串只有a或者c或者e长度是1。这个区别直接决定了状态转移方程长什么样。那为什么这道题要用动态规划因为暴力枚举所有子序列的复杂度是指数级的。假设两个字符串长度分别是m和n第一个字符串有2^m个子序列第二个有2^n个两两比对根本不可行。而动态规划能把问题拆成重叠子问题用一张二维表把中间结果存下来时间复杂度降到O(m×n)空间复杂度也是O(m×n)。对于训练营里常见的字符串长度通常不超过1000这个复杂度完全够用。这道题适合谁来学我的判断是如果你已经理解了动态规划的基本套路——比如爬楼梯、01背包——但还不太会处理“两个序列之间做匹配”这类问题那LCS就是最好的过渡题。它比背包问题更直观因为状态定义几乎是把题目要求直接翻译成数学语言但它又比单序列DP多了一个维度能帮你建立“二维DP表”的思维框架。后面你要学的编辑距离、最长递增子序列、正则匹配本质上都是LCS的变体。我在训练营里带过不少人发现一个规律能独立把LCS写对的人后面学编辑距离基本不会卡而LCS没搞透的人遇到编辑距离就会陷入“知道要填表但不知道怎么填”的状态。所以这15分不是白给的它是一块试金石。接下来我会从状态定义、转移方程推导、代码实现、空间优化、常见错误五个层面把这道题彻底拆开。你跟着走一遍以后遇到任何二维DP都不会慌。2. 状态定义与转移方程把“公共”两个字翻译成数学2.1 为什么dp[i][j]要定义成“前i个”和“前j个”动态规划的第一步永远是定义状态。对于LCS标准定义是dp[i][j]表示字符串A的前i个字符即A[0..i-1]和字符串B的前j个字符即B[0..j-1]的最长公共子序列长度。注意这里的下标含义——i和j是长度不是索引。也就是说dp[0][j]表示A取空串时的情况dp[i][0]表示B取空串时的情况。为什么不用“以A[i]和B[j]结尾”来定义因为子序列不要求连续以某个字符结尾并不能覆盖所有情况。比如AabcBac最长公共子序列是ac它不以A的最后一个字符c结尾吗其实以但如果我们定义成“以A[i]和B[j]结尾”那当A[i] ! B[j]时就无法从dp[i-1][j-1]转移过来因为结尾字符不匹配。而用“前i个”的定义dp[i][j]天然包含了“可以不选A[i]”和“可以不选B[j]”两种决策覆盖更全面。这个定义还有一个好处最终答案直接就是dp[m][n]不需要再遍历一遍找最大值。很多单序列DP题最后要扫一遍dp数组取最大但LCS不用因为dp[m][n]本身就表示“考虑完所有字符”的最优解。2.2 转移方程的两种情形字符相等与不相等状态定义清楚了转移方程就顺理成章。考虑dp[i][j]我们只看A的第i个字符即A[i-1]和B的第j个字符即B[j-1]情形一A[i-1] B[j-1]。这两个字符可以匹配上那它们一定可以贡献到公共子序列里。为什么说“一定可以”因为如果最优解不包含这一对匹配我们把它加进去也不会破坏顺序——A[i-1]和B[j-1]分别是两个字符串的末尾加进去只会让长度1。所以此时dp[i][j] dp[i-1][j-1] 1。情形二A[i-1] ! B[j-1]。这两个字符不相等那它们不可能同时出现在公共子序列的同一个位置上。但我们可以选择“放弃A的最后一个字符”或者“放弃B的最后一个字符”取两者中较大的那个。所以dp[i][j] max(dp[i-1][j], dp[i][j-1])。这里有一个常见的困惑为什么不考虑dp[i-1][j-1]因为dp[i-1][j-1]已经被dp[i-1][j]和dp[i][j-1]包含了。dp[i-1][j]表示A的前i-1个和B的前j个的LCS它至少不会比dp[i-1][j-1]小因为B多考虑了一个字符LCS长度只可能不变或增加。所以取max的时候不需要再单独看dp[i-1][j-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])2.3 边界条件空串的LCS长度是0边界条件很直观dp[0][j] 0对于所有jdp[i][0] 0对于所有i。因为空串和任何字符串的公共子序列只能是空串长度是0。在代码里我们通常把dp数组初始化成(m1)×(n1)的全零矩阵这样边界自动就对了不需要额外写循环。但这里有个细节dp数组的大小是(m1)×(n1)而不是m×n。多出来的那一行一列就是用来表示空串的。很多初学者会开成m×n然后发现处理i0或j0的时候要特判代码写得很乱。记住这个“多开一行一列”的技巧后面所有二维DP都适用。2.4 遍历顺序为什么是从左上到右下转移方程里dp[i][j]依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]这三个位置都在dp[i][j]的左边、上边或左上角。所以只要按照i从小到大、j从小到大的顺序遍历计算dp[i][j]时它依赖的所有值都已经算好了。这就是所谓的“填表法”。如果你尝试从右下往左上遍历那dp[i][j]依赖的值还没算出来就会出错。所以遍历顺序不是随便定的它由依赖关系决定。这一点在面试时经常被问到“你为什么这样遍历”答“因为状态转移的方向决定了必须从左上到右下”就对了。3. 代码实现从二维数组到滚动数组的完整过程3.1 标准二维DP写法先给出最直观的二维数组实现用Python演示def lcs_length(A, B): m, n len(A), len(B) # 多开一行一列dp[i][j]表示A前i个和B前j个的LCS长度 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(m×n)空间复杂度也是O(m×n)。对于训练营的题目字符串长度通常不超过1000所以二维数组完全没问题。但如果你在面试中被追问“能不能优化空间”就需要用到滚动数组。3.2 滚动数组优化为什么可以只保留两行观察转移方程dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。也就是说计算第i行的时候只需要第i-1行的数据更早的行已经没用了。所以我们可以把二维数组压缩成两行一行表示“上一行”一行表示“当前行”。但这里有个坑dp[i][j]依赖dp[i-1][j-1]也就是上一行的左上角。如果我们直接用一维数组原地更新dp[j-1]在计算dp[j]之前可能已经被更新成当前行的值了导致拿到错误的数据。所以要么用两个数组交替要么用一个临时变量保存左上角的值。先看两行交替的写法def lcs_length_2rows(A, B): 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 # 交换prev变成当前行curr复用为下一行 # 注意交换后curr里还是旧数据但下一轮会覆盖不影响 return prev[n]这里有个细节交换之后curr里还留着上一轮的数据但下一轮循环会从j1开始逐个覆盖所以不需要手动清零。但curr[0]始终是0因为dp[i][0]0这个位置不会被覆盖正好符合边界条件。3.3 一维数组临时变量更极致的空间优化如果还想再省一点可以只用一个一维数组外加一个变量记录左上角的值def lcs_length_1row(A, B): m, n len(A), len(B) dp [0] * (n 1) for i in range(1, m 1): prev_diag 0 # 记录dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 保存当前dp[j]它其实是上一行的dp[i-1][j] if A[i-1] B[j-1]: dp[j] prev_diag 1 else: dp[j] max(dp[j], dp[j-1]) prev_diag temp # 更新左上角的值 return dp[n]这段代码稍微难理解一点。关键在于prev_diag的更新时机在计算dp[j]之前dp[j]里存的是上一行的值即dp[i-1][j]我们把它暂存到temp计算完dp[j]后temp就变成了下一轮j1所需的左上角值即dp[i-1][j]。而dp[j-1]在计算dp[j]时已经是当前行的值了即dp[i][j-1]正好符合转移方程的需求。空间复杂度从O(m×n)降到了O(n)如果n比m大可以交换A和B让n取较小值进一步节省空间。这个优化在面试中很加分但训练营的15分题通常不要求写二维版本就够。3.4 不同语言的实现差异如果用C或Java二维数组的写法类似但要注意数组初始化。C里vectorvectorint dp(m1, vectorint(n1, 0))是标准写法Java里int[][] dp new int[m1][n1]默认就是0不需要手动填充。Python的列表推导式[[0]*(n1) for _ in range(m1)]要注意不能用[[0]*(n1)]*(m1)因为那样所有行共享同一个列表引用修改一行会影响所有行。这个坑我在训练营里见过至少五个人踩过调试半天找不到原因。4. 实测中的意外情况那些让代码跑不对的细节4.1 下标越界为什么你的循环从1开始初学者最容易犯的错误是循环写成for i in range(m)和for j in range(n)然后访问A[i-1]时变成A[-1]。在Python里A[-1]不会报错它会取最后一个字符导致结果完全错误在C或Java里直接越界崩溃。正确的做法是循环从1到m包含m访问字符时用A[i-1]。记住dp数组的下标是长度字符串的下标是位置两者差1。4.2 字符比较的陷阱大小写和空格题目通常给的是纯字母字符串但有些变体题会包含空格或数字。如果题目没有明确说明默认按字符的ASCII值比较。但要注意如果输入是从文件或标准输入读入的可能会带上换行符或空格。我在训练营里见过有人用input()读字符串结果末尾多了个\n导致最后一个字符永远匹配不上。解决办法是用strip()去掉首尾空白或者用sys.stdin.readline().strip()。4.3 空串输入边界条件有没有覆盖如果A或B是空串dp[m][n]应该返回0。二维数组初始化成全零循环从1开始如果m0或n0循环体根本不执行直接返回dp[0][n]或dp[m][0]都是0没问题。但如果你用了滚动数组prev初始化为全零交换后返回prev[n]也是0。所以标准写法天然处理了空串不需要特判。但如果你在代码里加了if not A or not B: return 0也不会错只是多余。4.4 超长字符串递归会爆栈DP不会有些训练营的测试用例字符串长度达到10^4这时候O(m×n)的DP表有10^8个元素内存可能吃紧。如果题目只要求长度不要求具体子序列可以用滚动数组把空间降到O(n)。但如果n也很大比如10^5那O(m×n)的时间复杂度就过不去了需要用更高级的算法如Hunt-Szymanski算法或后缀自动机。不过训练营的15分题通常不会这么变态字符串长度一般在1000以内二维DP足够。4.5 多组输入每次都要重新初始化有些题目会要求处理多组测试数据每组两个字符串。这时候要注意dp数组必须在每组数据开始时重新初始化不能复用上一组的结果。如果你把dp定义在循环外面第二组数据就会带着第一组的残留值答案肯定错。我建议把整个LCS函数封装起来每次调用都新建dp数组这样最安全。5. 从LCS到编辑距离同一套思维框架的延伸5.1 编辑距离的状态定义对比LCS和编辑距离Levenshtein Distance是二维DP里最经典的两道题它们的dp表结构几乎一样但转移方程不同。编辑距离的dp[i][j]表示A的前i个字符转换成B的前j个字符所需的最少操作次数操作包括插入、删除、替换。转移方程是if A[i-1] B[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])对比LCS你会发现编辑距离在字符不相等时多了一个dp[i-1][j-1]的选项对应替换操作而LCS不需要考虑替换因为子序列不要求字符一一对应。理解了LCS编辑距离只需要改一行代码。5.2 最长递增子序列一维DP到二维DP的桥梁最长递增子序列LIS通常用一维DP或贪心二分来做但它和LCS有一个巧妙的转化如果把原序列排序后去重再和原序列求LCS得到的就是LIS长度。这个转化在面试中经常被用来考察你是否真正理解LCS的适用场景。不过要注意排序后的序列和原序列求LCS时相同的元素可能被重复匹配所以需要去重或者用严格递增的条件。这个技巧在训练营里属于进阶内容但思路值得了解。5.3 回文子序列把LCS应用到自身最长回文子序列LPS可以转化为原字符串和它的反转字符串求LCS。因为回文子序列正着读和反着读一样所以它一定是原字符串和反转字符串的公共子序列。这个转化非常优雅代码只需要把LCS的第二个参数改成A[::-1]即可。我在实际做题时遇到回文相关的DP题第一反应就是能不能转成LCS往往能省很多推导时间。5.4 实际工程中的应用场景LCS不只是一道算法题它在实际工程中有很多应用。比如Git的diff功能本质上就是求两个文件版本的LCS然后标记出新增和删除的行。再比如DNA序列比对生物信息学里用LCS来找出两个基因序列的相似片段。还有拼写检查、抄袭检测、版本控制底层都有LCS的影子。所以这道15分题不是考完就忘的它是很多实际系统的算法基础。6. 训练营里的实战建议怎么练才能一次写对6.1 手写dp表不要一上来就写代码我建议你在第一次做这道题时拿一张纸画一个(m1)×(n1)的表格手动填一遍。比如AabcdeBace从dp[0][0]开始一行一行填到dp[5][3]。填完之后你会对转移方程有肌肉记忆以后写代码时脑子里能浮现出表格的形态。这个习惯我保持了很长时间遇到新的二维DP题都会先手推小样例确认转移方程正确后再写代码。6.2 测试用例要覆盖三种情况写完代码后至少用三组数据测试第一组两个字符串有公共子序列且长度大于0第二组两个字符串完全没有公共字符答案应该是0第三组其中一个字符串是空串答案也是0。如果这三组都过了基本逻辑就没问题。进阶一点可以测试两个字符串完全相同的情况答案应该等于字符串长度以及一个字符串是另一个的子序列的情况。6.3 面试中的追问如何输出具体的子序列训练营只要求长度但面试官可能会追问“怎么把具体的子序列打印出来”。这时候需要从dp[m][n]往回走如果A[i-1] B[j-1]说明这个字符属于LCS记录下来然后i和j都减1否则比较dp[i-1][j]和dp[i][j-1]往大的方向走。最后把记录的字符反转就是答案。这个过程叫“回溯路径”是LCS的常见扩展。6.4 常见错误清单我把训练营里学员最常犯的错误整理成一张表你写完代码后可以对照检查错误类型具体表现修正方法下标越界循环从0开始访问A[i-1]变成A[-1]循环从1到m字符索引用i-1数组初始化错误Python用[[0]*(n1)]*(m1)导致行共享用列表推导式逐行创建边界未处理dp数组开成m×ni0或j0时特判开(m1)×(n1)初始化全零遍历顺序错误从右下往左上填表从左上到右下i和j都递增滚动数组覆盖一维数组原地更新时左上角被覆盖用临时变量保存dp[i-1][j-1]多组输入未重置dp数组定义在循环外残留上一组数据每组数据重新初始化dp6.5 时间分配建议在训练营的限时环境中这道15分题建议在10分钟内完成2分钟理解题意和确认状态定义3分钟写代码3分钟测试边界2分钟检查下标和初始化。如果你超过15分钟还在调试说明对二维DP的套路还不够熟建议回去把背包问题再刷几道建立“多开一行一列”和“从左上到右下填表”的条件反射。我个人在实际做题和带人过程中发现LCS这道题的价值不在于它本身有多难而在于它是二维DP的“最小可行模型”。你把这道题吃透后面遇到任何需要两个维度做匹配的问题——比如字符串匹配、路径规划、资源分配——都能快速套用同样的思维框架。所以别嫌它只有15分把它当成一把钥匙打开的是整个二维动态规划的大门。