1143 最长公共子序列LeetCode 上一道中等难度的经典动态规划题。我第一次做的时候光是在“要不要连续匹配”这个问题上就纠结了半天后来发现只要把“子序列”和“子串”的区别想透后面一切顺理成章。这篇我会把从暴力到动态规划、从二维到一维优化的完整过程拆开讲顺便把我在调试时踩过的几个坑也一并写出来。正在刷题准备面试的或者工作里要处理字符串相似度的都可以直接参考里面的代码和思路。1. 核心思路子序列问题为什么得用动态规划1.1 先把“子序列”和“子串”掰扯清楚很多人第一次看到“最长公共子序列”时脑子里浮现的是“最长公共子串”然后下意识想用滑窗、双指针去解。这一步如果跑偏整道题就会一直卡在错误的方向上。子串要求连续比如abcde里的bcd是连续的一段。子序列不要求连续只要求保持相对顺序。举个例子text1 abcdetext2 acde那么ace是两者的公共子序列在text1中取第 1、3、5 个字符在text2中取第 1、3、4 个字符取出来的a、c、e在两边都保持“a 在 c 前面c 在 e 前面”的顺序。但ace不是两个字符串的公共子串因为它在text2里并不连续。这个区别直接决定了题目的解法方向。子串问题可以用滑窗、后缀数组、KMP 等连续匹配手段子序列问题因为允许跳过字符问题空间一下子变得非常大必须换一种思路。我自己面试别人的时候经常先问一句“子序列和子串有什么不同”能立刻分清不少候选人到底有没有真正理解题意。1.2 暴力枚举的复杂度是魔鬼动态规划才能救命既然每个字符都可以“选”或“不选”那枚举text1的所有子序列就是 2 的 m 次方种m 是text1长度。每枚举出一个子序列还要去text2里检查它是否存在这个检查就算用哈希优化也免不了 O(n) 级别的工作。整体复杂度接近 O(2^m × n)m 到 25 左右就已经跑不动了更别说 LeetCode 上给到 1000 级别的长度。动态规划能救命的点在于这个问题有重叠子问题和最优子结构。text1[0:i]和text2[0:j]的最长公共子序列长度可以由更短的字符串前缀推导出来。每次决策都是“当前这两个字符要不要配成一对”而不需要重新枚举所有组合。换句话说我们把一个指数爆炸的搜索问题压缩成一张 m×n 的表逐格填充这就是 DP 最核心的动机。2. 状态设计与转移方程四步推出核心递推式2.1 状态定义为什么是 dp[i][j]而不是别的写法设dp[i][j]表示text1的前i个字符组成的子串和text2的前j个字符组成的子串它们的最长公共子序列长度。这里的关键是“前缀”而不是“以某个字符结尾”。子串类 DP 喜欢用“以当前位置结尾”作为状态比如最长公共子串的dp[i][j]表示以text1[i]、text2[j]结尾的公共子串长度因为子串必须连续结尾位置能锁定连续段。子序列不连续用“前 i 个字符”这种前缀定义天然表达了“我已经扫描到了哪个位置目前很可能没配完但前面已经攒了多长的公共子序列”。一旦想清楚这个区别写状态就顺了。边界条件也很直接如果其中一个字符串是空的那公共子序列长度只能是 0。所以dp[0][j] 0dp[i][0] 0。这也是为什么后面代码里 dp 数组要比字符串长度都多开一列、一行用 0 来兜底。2.2 转移方程推导相等和不相等两句话就能说清现在看两个字符串各自的第i和第j个字符也就是text1[i-1]和text2[j-1]。只有两种情况。第一两个字符相等。既然它们相等就可以把这对字符作为当前公共子序列的最后一个配对接到text1前i-1个字符、text2前j-1个字符已经形成的最长公共子序列后面。所以dp[i][j] dp[i-1][j-1] 1注意这里必须从dp[i-1][j-1]转移而不是从dp[i-1][j]或dp[i][j-1]加一。如果从dp[i-1][j]加一意味着一对相等的字符可能被重复计算或者破坏了原有顺序。这个错误非常隐蔽后面我会专门讲。第二两个字符不相等。既然当前这对字符没法组成公共子序列的最后一位那答案只能来自两种情况要么忽略text1[i-1]看dp[i-1][j]要么忽略text2[j-1]看dp[i][j-1]。取较大值dp[i][j] max(dp[i-1][j], dp[i][j-1])有人会问为什么不比较dp[i-1][j-1]呢因为dp[i-1][j]和dp[i][j-1]都已经覆盖了dp[i-1][j-1]的情况而且它们各自身后的选择只会更充分所以在 max 比较里不需要重复列出来。整个转移方程下来计算顺序就很清楚了dp[i][j]依赖左上方dp[i-1][j-1]、正上方dp[i-1][j]和左方dp[i][j-1]因此从i从小到大、j从小到大逐行填充即可。这个顺序后面写代码时直接对应循环嵌套。2.3 手填一张dp表让递推式看得见摸得着理论说再多不如亲手填一次表。我拿text1 abcdetext2 ace来演算最终结果应该是 3因为最长公共子序列就是ace。表格的行代表text1的前缀列代表text2的前缀第一行和第一列全是 0。dp空ace空0000a0111b0111c0122d0122e0123填表时你会发现一个规律每一行都是从左上角向右下角不断“累积”出来的。遇到text1[i-1]与text2[j-1]相等的地方比如a和a值会从左上角的 0 变 1c和c相遇时左上角是 1于是变成 2e和e相遇时左上角是 2于是变成 3。不相等的位置永远只取上方和左方较大的那个值所以数字不会倒退。这张表填完动态规划就不再是抽象公式而是看得见摸得着的计算过程。3. 代码实现与空间优化从 O(mn) 到 O(min(m,n))3.1 先写一版朴素二维 DP保证逻辑正确根据上面的递推式最直观的写法就是开一个二维数组。我先给 Python 版本做演示思路最干净。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[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)整个表都留在内存里。如果只想求长度这张表显然有很多行是用完就没用的。这也是下一步优化的切入点。在 LeetCode 上跑类似数据时O(mn) 的时间基本是必须的成本但空间是可以压缩的。写代码前我会先做一步“短串判断”如果text1比text2短就先交换两者。原因是 LCS 是对称的交换两个字符串不影响最终答案但能把经典二维写法的内层循环长度固定为较短那一个减少不少无谓空间。当然二维版本里这个操作只是锦上添花真正的好处要到一维优化才明显。3.2 滚动数组的原理只保留上一行和当前行观察二维表填充过程计算dp[i][j]的时候只会用到第i-1行上一行和第i行当前已经算出来的左边格子。更早的行根本不会再用。所以最直接的优化是用两行数组滚动复用prev[j]保存上一行的第 j 列cur[j]保存当前行的第 j 列每算完一行交换prev和cur。这样的空间是 O(2n)也就是 O(n)。两行数组版本比二维好理解逻辑直接从表上搬下来不容易写错。但它还不是终点因为我们可以再用一个变量把“左上角”也省下来把两行压成一行。这也是面试官比较爱追问的进阶点。3.3 一维数组版本小心保存“左上角”一维数组的核心思路是只保留一个长度为n1的数组dp每轮循环开始时dp中保存的是上一行的结果。当我在这一行中更新dp[j]时更新前的dp[j]就是上一行的dp[i-1][j]而刚更新过的dp[j-1]是当前行的dp[i][j-1]。真正麻烦的是左上角dp[i-1][j-1]它在dp[j-1]被覆盖后就已经丢了必须用一个临时变量提前保存下来。给你一个可以直接跑的 Python 一维版本class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: if len(text1) len(text2): text1, text2 text2, text1 m, n len(text1), len(text2) dp [0] * (n 1) for i in range(1, m 1): left_up 0 for j in range(1, n 1): tmp dp[j] if text1[i - 1] text2[j - 1]: dp[j] left_up 1 else: dp[j] max(dp[j], dp[j - 1]) left_up tmp return dp[n]这里有一个特别容易踩的坑为什么不能用 0/1 背包那种“倒序遍历”来保留上一行数据因为 LCS 的状态转移依赖当前行左侧的dp[j-1]而倒序遍历会先更新右侧导致左侧dp[j-1]还是上一行的旧值最终结果全错。正确做法就是正序遍历加left_up变量。每次循环开始left_up都要重置为 0因为它代表上一行的dp[0]也就是边界 0。我再给一段 C 参考逻辑完全一样方便用 C 刷题的朋友直接对照class Solution { public: int longestCommonSubsequence(string text1, string text2) { if (text1.size() text2.size()) swap(text1, text2); int m text1.size(), n text2.size(); vectorint dp(n 1, 0); for (int i 1; i m; i) { int leftUp 0; for (int j 1; j n; j) { int tmp dp[j]; if (text1[i - 1] text2[j - 1]) { dp[j] leftUp 1; } else { dp[j] max(dp[j], dp[j - 1]); } leftUp tmp; } } return dp[n]; } };因为提前交换了字符串让较短的字符串作为内层循环的列数所以一维数组长度是min(m, n) 1空间复杂度从 O(mn) 降到了 O(min(m,n))。时间上依然是 O(mn)这已经是比较理想的结果。如果面试官问“还能不能再优化时间”本质上很难因为至少要把两个字符串里的字符两两比较一遍。4. 易错点与调试实录这些坑我基本都踩过4.1 下标偏移和空字符串边界写 LCS 代码最常见的低级错误就是下标越界或者漏掉空串场景。因为dp数组要比字符串长度大 1访问字符时使用的是text1[i - 1]而不是text1[i]。我第一次从“以 i 结尾”的 DP 习惯切过来时就经常手滑写成text1[i]然后整段代码崩掉。空串边界通常不会主动出错因为初始化已经覆盖但如果你在循环里额外判断m 0 or n 0返回值必须写 0。其实二维数组初始化后dp[m][n]自动就是 0不需要特殊分支。写代码时不要画蛇添足越简单越不容易错。4.2 相等分支与不相等分支的写法误区有几种错误写法我都见过甚至亲手写过。第一种是相等时写成dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) 1。这个看起来“兼顾了上左两边的最大值”其实会重复计数。比如text1 atext2 aa到i1, j2时如果取左边dp[1][1] 1再加 1会得到 2但实际最长公共子序列长度只能是 1。相等就意味着这对字符必须用来配对直接使用左上角不要画蛇添足。第二种是漏掉不相等分支的max直接在循环里continue或者不赋值这样dp[i][j]会保留初始值 0后续所有位置的计算都会出错。每次循环必须显式给dp[i][j]赋一个值要么是相等分支的结果要么是不相等分支的结果。第三种是把相等分支和不相等分支写反。逻辑上不相等时还能通过忽略一个字符来延续旧的长度但绝对不能让dp[i][j]变成更小。如果不小心写了min基本上一大半测试用例都会挂。4.3 回溯输出最长公共子序列力扣 1143 只要求返回长度但面试里经常会被追问“把最长公共子序列打印出来”。回溯的思路是从dp[m][n]倒着走如果当前位置两个字符相等说明这个字符被选中记录后同时向左上移动如果不相等比较上方和左方哪个更大往大的一方移动。写出来是这样的def print_lcs(text1: str, text2: str, dp) - str: i, j len(text1), len(text2) res [] while i 0 and j 0: if text1[i - 1] text2[j - 1]: res.append(text1[i - 1]) i - 1 j - 1 elif dp[i - 1][j] dp[i][j - 1]: i - 1 else: j - 1 return .join(reversed(res))这里有个细节要注意当上方和左方的值相等时随便选一边走都能得到“某一个”最长公共子序列但不一定是同一个。比如text1 abctext2 ac在某个位置上方和左方可能都是 1走不同分支会得到不同结果长度都正确。理解了这一点回溯就不会被“我为什么没打出来预期字符串”这种问题卡住。4.4 一维优化后最容易出的错一维版本的出错点集中在那一个tmp变量上。很多人知道要用left_up但把它赋值的位置写错了。注意必须在dp[j]被覆盖之前先用tmp dp[j]保存旧值整个循环结束前再left_up tmp。如果顺序反了下一轮 j 拿到的left_up就是已经被覆盖的当前行数据结果必然出错。还有一点就是初始化left_up的位置。它必须在外层循环的每行开始时重置为 0不能声明在两层循环外面。否则第二行之后的左上角数据全是上一行带下来的脏数据。我自己调试时就因为偷懒把变量定义到了外层外层结果整张表从第二行开始全错排查了半天才意识到。5. 从1143看真实应用LCS 不止是一道面试题5.1 文本 diff 与版本管理LCS 最早的经典应用之一就是文本对比。两个版本的源代码、文档之间哪些行是新增、哪些是删除本质上可以理解为先找到两个文本的最长公共子序列作为“未变化部分”剩下的段落就是插入或删除的内容。很多diff工具和版本管理系统的核心思路都起源于这里。不过工程上的git diff并不会直接用最朴素的 LCS因为那个实现时间和空间都太高实际操作会用 Myers diff 算法等变体。Myers 算法在 LCS 的基础上加入了“短编辑脚本”的贪心思路让差异输出更符合人的阅读习惯。但不管它怎么优化LCS 这个理论基础是不会变的。我工作里写代码审查插件时内部就有一层相似的逻辑用来判断两个代码片段是否“本质相同、局部调整”。5.2 生物信息学里的序列比对DNA 序列由四种碱基组成判断两条序列有多相似一个朴素方法就是找它们的公共子序列。在生物信息学领域Needleman-Wunsch 全局比对算法和 Smith-Waterman 局部比对算法本质上都是在 LCS 框架上加上了替换罚分、gap 罚分等更复杂的评分体系。你要是先把 1143 的转移方程吃透再去看这些算法会觉得它们的表格填充过程异常熟悉只是每一格的计算从“比大小”变成了“算分数”。我当时看这类算法时最大的感受是算法题的模型往往不是凭空设计的而是从现实问题里抽象出来的。LCS 能同时出现在教科书、面试题和基因工程软件里说明它这个“在保留顺序前提下找公共部分”的抽象确实抓住了非常广泛的一类问题。5.3 一个奇妙的转换LIS 到 LCS还有一个很有意思的脑洞最长递增子序列LIS问题可以转换成 LCS。方法是把原数组排序并去重得到一个新数组然后求原数组和新数组的 LCS长度就是原数组的 LIS 长度。道理很简单排好序的数组保证了递增顺序LCS 在这两个数组之间能配上的字符必然是在原数组中出现顺序和大小顺序都一致的上升序列。不过要注意直接用这个转换去解 LIS 会有两个问题一是复杂度 O(n²)比专门的“贪心 二分”O(n log n) 慢太多二是排序必须去重否则重复数字可能被重复选进子序列那就不是严格的递增了。所以它更多是作为一种思维模型存在用来帮助理解 LIS 与 LCS 之间的关系而不是实际求解的最佳手段。5.4 延伸方向编辑距离与最长公共子串刷完 1143 之后我建议顺着同一棵知识树继续看两个题目LeetCode 72 编辑距离、LeetCode 718 最长重复子数组最长公共子串的数组版。编辑距离的 dp 状态也是dp[i][j]只是转移变成了“插入、删除、替换”三种操作取最小值最长公共子串则把状态定义改成“以当前字符结尾”不相等时直接清零并记录最大值。三者对照着看你会发现“什么时候用前缀状态、什么时候用结尾状态、什么时候允许跳过、什么时候必须连续”这个判断能力才是动态规划题真正的分水岭。我个人在实际刷题中的体会是这类二维 DP 题一定不要只看题解得找一组简单数据亲手画一遍表格。填完那一次之后转移方程不再需要背一维优化也变成顺理成章的事情。字符串长度为 1000 左右的测试用例在 LeetCode 上很常见一行一列画出来虽然费纸但耗费的十分钟比反复看十遍代码都值。
1143 最长公共子序列LeetCode 上一道中等难度的经典动态规划题。我第一次做的时候光是在“要不要连续匹配”这个问题上就纠结了半天后来发现只要把“子序列”和“子串”的区别想透后面一切顺理成章。这篇我会把从暴力到动态规划、从二维到一维优化的完整过程拆开讲顺便把我在调试时踩过的几个坑也一并写出来。正在刷题准备面试的或者工作里要处理字符串相似度的都可以直接参考里面的代码和思路。1. 核心思路子序列问题为什么得用动态规划1.1 先把“子序列”和“子串”掰扯清楚很多人第一次看到“最长公共子序列”时脑子里浮现的是“最长公共子串”然后下意识想用滑窗、双指针去解。这一步如果跑偏整道题就会一直卡在错误的方向上。子串要求连续比如abcde里的bcd是连续的一段。子序列不要求连续只要求保持相对顺序。举个例子text1 abcdetext2 acde那么ace是两者的公共子序列在text1中取第 1、3、5 个字符在text2中取第 1、3、4 个字符取出来的a、c、e在两边都保持“a 在 c 前面c 在 e 前面”的顺序。但ace不是两个字符串的公共子串因为它在text2里并不连续。这个区别直接决定了题目的解法方向。子串问题可以用滑窗、后缀数组、KMP 等连续匹配手段子序列问题因为允许跳过字符问题空间一下子变得非常大必须换一种思路。我自己面试别人的时候经常先问一句“子序列和子串有什么不同”能立刻分清不少候选人到底有没有真正理解题意。1.2 暴力枚举的复杂度是魔鬼动态规划才能救命既然每个字符都可以“选”或“不选”那枚举text1的所有子序列就是 2 的 m 次方种m 是text1长度。每枚举出一个子序列还要去text2里检查它是否存在这个检查就算用哈希优化也免不了 O(n) 级别的工作。整体复杂度接近 O(2^m × n)m 到 25 左右就已经跑不动了更别说 LeetCode 上给到 1000 级别的长度。动态规划能救命的点在于这个问题有重叠子问题和最优子结构。text1[0:i]和text2[0:j]的最长公共子序列长度可以由更短的字符串前缀推导出来。每次决策都是“当前这两个字符要不要配成一对”而不需要重新枚举所有组合。换句话说我们把一个指数爆炸的搜索问题压缩成一张 m×n 的表逐格填充这就是 DP 最核心的动机。2. 状态设计与转移方程四步推出核心递推式2.1 状态定义为什么是 dp[i][j]而不是别的写法设dp[i][j]表示text1的前i个字符组成的子串和text2的前j个字符组成的子串它们的最长公共子序列长度。这里的关键是“前缀”而不是“以某个字符结尾”。子串类 DP 喜欢用“以当前位置结尾”作为状态比如最长公共子串的dp[i][j]表示以text1[i]、text2[j]结尾的公共子串长度因为子串必须连续结尾位置能锁定连续段。子序列不连续用“前 i 个字符”这种前缀定义天然表达了“我已经扫描到了哪个位置目前很可能没配完但前面已经攒了多长的公共子序列”。一旦想清楚这个区别写状态就顺了。边界条件也很直接如果其中一个字符串是空的那公共子序列长度只能是 0。所以dp[0][j] 0dp[i][0] 0。这也是为什么后面代码里 dp 数组要比字符串长度都多开一列、一行用 0 来兜底。2.2 转移方程推导相等和不相等两句话就能说清现在看两个字符串各自的第i和第j个字符也就是text1[i-1]和text2[j-1]。只有两种情况。第一两个字符相等。既然它们相等就可以把这对字符作为当前公共子序列的最后一个配对接到text1前i-1个字符、text2前j-1个字符已经形成的最长公共子序列后面。所以dp[i][j] dp[i-1][j-1] 1注意这里必须从dp[i-1][j-1]转移而不是从dp[i-1][j]或dp[i][j-1]加一。如果从dp[i-1][j]加一意味着一对相等的字符可能被重复计算或者破坏了原有顺序。这个错误非常隐蔽后面我会专门讲。第二两个字符不相等。既然当前这对字符没法组成公共子序列的最后一位那答案只能来自两种情况要么忽略text1[i-1]看dp[i-1][j]要么忽略text2[j-1]看dp[i][j-1]。取较大值dp[i][j] max(dp[i-1][j], dp[i][j-1])有人会问为什么不比较dp[i-1][j-1]呢因为dp[i-1][j]和dp[i][j-1]都已经覆盖了dp[i-1][j-1]的情况而且它们各自身后的选择只会更充分所以在 max 比较里不需要重复列出来。整个转移方程下来计算顺序就很清楚了dp[i][j]依赖左上方dp[i-1][j-1]、正上方dp[i-1][j]和左方dp[i][j-1]因此从i从小到大、j从小到大逐行填充即可。这个顺序后面写代码时直接对应循环嵌套。2.3 手填一张dp表让递推式看得见摸得着理论说再多不如亲手填一次表。我拿text1 abcdetext2 ace来演算最终结果应该是 3因为最长公共子序列就是ace。表格的行代表text1的前缀列代表text2的前缀第一行和第一列全是 0。dp空ace空0000a0111b0111c0122d0122e0123填表时你会发现一个规律每一行都是从左上角向右下角不断“累积”出来的。遇到text1[i-1]与text2[j-1]相等的地方比如a和a值会从左上角的 0 变 1c和c相遇时左上角是 1于是变成 2e和e相遇时左上角是 2于是变成 3。不相等的位置永远只取上方和左方较大的那个值所以数字不会倒退。这张表填完动态规划就不再是抽象公式而是看得见摸得着的计算过程。3. 代码实现与空间优化从 O(mn) 到 O(min(m,n))3.1 先写一版朴素二维 DP保证逻辑正确根据上面的递推式最直观的写法就是开一个二维数组。我先给 Python 版本做演示思路最干净。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[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)整个表都留在内存里。如果只想求长度这张表显然有很多行是用完就没用的。这也是下一步优化的切入点。在 LeetCode 上跑类似数据时O(mn) 的时间基本是必须的成本但空间是可以压缩的。写代码前我会先做一步“短串判断”如果text1比text2短就先交换两者。原因是 LCS 是对称的交换两个字符串不影响最终答案但能把经典二维写法的内层循环长度固定为较短那一个减少不少无谓空间。当然二维版本里这个操作只是锦上添花真正的好处要到一维优化才明显。3.2 滚动数组的原理只保留上一行和当前行观察二维表填充过程计算dp[i][j]的时候只会用到第i-1行上一行和第i行当前已经算出来的左边格子。更早的行根本不会再用。所以最直接的优化是用两行数组滚动复用prev[j]保存上一行的第 j 列cur[j]保存当前行的第 j 列每算完一行交换prev和cur。这样的空间是 O(2n)也就是 O(n)。两行数组版本比二维好理解逻辑直接从表上搬下来不容易写错。但它还不是终点因为我们可以再用一个变量把“左上角”也省下来把两行压成一行。这也是面试官比较爱追问的进阶点。3.3 一维数组版本小心保存“左上角”一维数组的核心思路是只保留一个长度为n1的数组dp每轮循环开始时dp中保存的是上一行的结果。当我在这一行中更新dp[j]时更新前的dp[j]就是上一行的dp[i-1][j]而刚更新过的dp[j-1]是当前行的dp[i][j-1]。真正麻烦的是左上角dp[i-1][j-1]它在dp[j-1]被覆盖后就已经丢了必须用一个临时变量提前保存下来。给你一个可以直接跑的 Python 一维版本class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: if len(text1) len(text2): text1, text2 text2, text1 m, n len(text1), len(text2) dp [0] * (n 1) for i in range(1, m 1): left_up 0 for j in range(1, n 1): tmp dp[j] if text1[i - 1] text2[j - 1]: dp[j] left_up 1 else: dp[j] max(dp[j], dp[j - 1]) left_up tmp return dp[n]这里有一个特别容易踩的坑为什么不能用 0/1 背包那种“倒序遍历”来保留上一行数据因为 LCS 的状态转移依赖当前行左侧的dp[j-1]而倒序遍历会先更新右侧导致左侧dp[j-1]还是上一行的旧值最终结果全错。正确做法就是正序遍历加left_up变量。每次循环开始left_up都要重置为 0因为它代表上一行的dp[0]也就是边界 0。我再给一段 C 参考逻辑完全一样方便用 C 刷题的朋友直接对照class Solution { public: int longestCommonSubsequence(string text1, string text2) { if (text1.size() text2.size()) swap(text1, text2); int m text1.size(), n text2.size(); vectorint dp(n 1, 0); for (int i 1; i m; i) { int leftUp 0; for (int j 1; j n; j) { int tmp dp[j]; if (text1[i - 1] text2[j - 1]) { dp[j] leftUp 1; } else { dp[j] max(dp[j], dp[j - 1]); } leftUp tmp; } } return dp[n]; } };因为提前交换了字符串让较短的字符串作为内层循环的列数所以一维数组长度是min(m, n) 1空间复杂度从 O(mn) 降到了 O(min(m,n))。时间上依然是 O(mn)这已经是比较理想的结果。如果面试官问“还能不能再优化时间”本质上很难因为至少要把两个字符串里的字符两两比较一遍。4. 易错点与调试实录这些坑我基本都踩过4.1 下标偏移和空字符串边界写 LCS 代码最常见的低级错误就是下标越界或者漏掉空串场景。因为dp数组要比字符串长度大 1访问字符时使用的是text1[i - 1]而不是text1[i]。我第一次从“以 i 结尾”的 DP 习惯切过来时就经常手滑写成text1[i]然后整段代码崩掉。空串边界通常不会主动出错因为初始化已经覆盖但如果你在循环里额外判断m 0 or n 0返回值必须写 0。其实二维数组初始化后dp[m][n]自动就是 0不需要特殊分支。写代码时不要画蛇添足越简单越不容易错。4.2 相等分支与不相等分支的写法误区有几种错误写法我都见过甚至亲手写过。第一种是相等时写成dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) 1。这个看起来“兼顾了上左两边的最大值”其实会重复计数。比如text1 atext2 aa到i1, j2时如果取左边dp[1][1] 1再加 1会得到 2但实际最长公共子序列长度只能是 1。相等就意味着这对字符必须用来配对直接使用左上角不要画蛇添足。第二种是漏掉不相等分支的max直接在循环里continue或者不赋值这样dp[i][j]会保留初始值 0后续所有位置的计算都会出错。每次循环必须显式给dp[i][j]赋一个值要么是相等分支的结果要么是不相等分支的结果。第三种是把相等分支和不相等分支写反。逻辑上不相等时还能通过忽略一个字符来延续旧的长度但绝对不能让dp[i][j]变成更小。如果不小心写了min基本上一大半测试用例都会挂。4.3 回溯输出最长公共子序列力扣 1143 只要求返回长度但面试里经常会被追问“把最长公共子序列打印出来”。回溯的思路是从dp[m][n]倒着走如果当前位置两个字符相等说明这个字符被选中记录后同时向左上移动如果不相等比较上方和左方哪个更大往大的一方移动。写出来是这样的def print_lcs(text1: str, text2: str, dp) - str: i, j len(text1), len(text2) res [] while i 0 and j 0: if text1[i - 1] text2[j - 1]: res.append(text1[i - 1]) i - 1 j - 1 elif dp[i - 1][j] dp[i][j - 1]: i - 1 else: j - 1 return .join(reversed(res))这里有个细节要注意当上方和左方的值相等时随便选一边走都能得到“某一个”最长公共子序列但不一定是同一个。比如text1 abctext2 ac在某个位置上方和左方可能都是 1走不同分支会得到不同结果长度都正确。理解了这一点回溯就不会被“我为什么没打出来预期字符串”这种问题卡住。4.4 一维优化后最容易出的错一维版本的出错点集中在那一个tmp变量上。很多人知道要用left_up但把它赋值的位置写错了。注意必须在dp[j]被覆盖之前先用tmp dp[j]保存旧值整个循环结束前再left_up tmp。如果顺序反了下一轮 j 拿到的left_up就是已经被覆盖的当前行数据结果必然出错。还有一点就是初始化left_up的位置。它必须在外层循环的每行开始时重置为 0不能声明在两层循环外面。否则第二行之后的左上角数据全是上一行带下来的脏数据。我自己调试时就因为偷懒把变量定义到了外层外层结果整张表从第二行开始全错排查了半天才意识到。5. 从1143看真实应用LCS 不止是一道面试题5.1 文本 diff 与版本管理LCS 最早的经典应用之一就是文本对比。两个版本的源代码、文档之间哪些行是新增、哪些是删除本质上可以理解为先找到两个文本的最长公共子序列作为“未变化部分”剩下的段落就是插入或删除的内容。很多diff工具和版本管理系统的核心思路都起源于这里。不过工程上的git diff并不会直接用最朴素的 LCS因为那个实现时间和空间都太高实际操作会用 Myers diff 算法等变体。Myers 算法在 LCS 的基础上加入了“短编辑脚本”的贪心思路让差异输出更符合人的阅读习惯。但不管它怎么优化LCS 这个理论基础是不会变的。我工作里写代码审查插件时内部就有一层相似的逻辑用来判断两个代码片段是否“本质相同、局部调整”。5.2 生物信息学里的序列比对DNA 序列由四种碱基组成判断两条序列有多相似一个朴素方法就是找它们的公共子序列。在生物信息学领域Needleman-Wunsch 全局比对算法和 Smith-Waterman 局部比对算法本质上都是在 LCS 框架上加上了替换罚分、gap 罚分等更复杂的评分体系。你要是先把 1143 的转移方程吃透再去看这些算法会觉得它们的表格填充过程异常熟悉只是每一格的计算从“比大小”变成了“算分数”。我当时看这类算法时最大的感受是算法题的模型往往不是凭空设计的而是从现实问题里抽象出来的。LCS 能同时出现在教科书、面试题和基因工程软件里说明它这个“在保留顺序前提下找公共部分”的抽象确实抓住了非常广泛的一类问题。5.3 一个奇妙的转换LIS 到 LCS还有一个很有意思的脑洞最长递增子序列LIS问题可以转换成 LCS。方法是把原数组排序并去重得到一个新数组然后求原数组和新数组的 LCS长度就是原数组的 LIS 长度。道理很简单排好序的数组保证了递增顺序LCS 在这两个数组之间能配上的字符必然是在原数组中出现顺序和大小顺序都一致的上升序列。不过要注意直接用这个转换去解 LIS 会有两个问题一是复杂度 O(n²)比专门的“贪心 二分”O(n log n) 慢太多二是排序必须去重否则重复数字可能被重复选进子序列那就不是严格的递增了。所以它更多是作为一种思维模型存在用来帮助理解 LIS 与 LCS 之间的关系而不是实际求解的最佳手段。5.4 延伸方向编辑距离与最长公共子串刷完 1143 之后我建议顺着同一棵知识树继续看两个题目LeetCode 72 编辑距离、LeetCode 718 最长重复子数组最长公共子串的数组版。编辑距离的 dp 状态也是dp[i][j]只是转移变成了“插入、删除、替换”三种操作取最小值最长公共子串则把状态定义改成“以当前字符结尾”不相等时直接清零并记录最大值。三者对照着看你会发现“什么时候用前缀状态、什么时候用结尾状态、什么时候允许跳过、什么时候必须连续”这个判断能力才是动态规划题真正的分水岭。我个人在实际刷题中的体会是这类二维 DP 题一定不要只看题解得找一组简单数据亲手画一遍表格。填完那一次之后转移方程不再需要背一维优化也变成顺理成章的事情。字符串长度为 1000 左右的测试用例在 LeetCode 上很常见一行一列画出来虽然费纸但耗费的十分钟比反复看十遍代码都值。
