刷题打卡到第49天遇到的这道「1143. 最长公共子序列」可以说是我近期刷动态规划以来最有代表性的一道题。倒不是说它难而是它把 DP 的骨架给得非常清晰状态定义、状态转移、边界处理、空间优化每一步都有典型的思考路径而且几乎可以无缝迁移到后面一系列字符串类的DP问题编辑距离、正则表达式匹配、两个字符串的删除操作等。最长公共子序列Longest Common Subsequence也是算法面试里的常客很多出题人喜欢把它当作中等难度题出现本质上考你两件事第一能不能想到用二维动态规划第二能不能把空间从 O(mn) 压缩到 O(n)。如果你正准备面试或者刚开始系统刷 DP这篇文章建议认真读完。我会从暴力递归讲起一路推到二维DP再做空间优化最后聊聊打印具体子序列和相关的变体题全程用可复现代码和实例保证你能跟着推一遍就真正吃透。1. 先搞懂“子序列”定义不然代码写得再快也是白写很多人容易把这道题和“最长公共子串”搞混但子序列和子串是两回事。子串要求连续比如abc在abdec里只能取出ab或dec中间断开的取不了。而子序列只要求相对顺序一致不要求连续。abc在abdec里可以通过取第 0、1、3 个字符得到abc这就是一个子序列。搞清楚这个区别之后再来看题目给定字符串text1和text2需要返回它们的最长公共子序列的长度。如果不存在公共子序列就返回 0。一个容易被忽略的细节是子序列可以是不连续的所以两个很长的字符串哪怕中间碎成渣只要挑出来的字符顺序一致它就是一个合法的公共子序列。这个“允许跳过字符”的特性直接决定了这道题不能用滑窗或双指针去硬解而是要用 DP 去枚举“跳过哪些字符、保留哪些字符”的所有可能性。1.1 为什么不能用双指针或哈希表我见过不少第一次做这道题的同学第一反应是用两个指针分别扫两个字符串遇到相同的字符就记录不同就移动某个指针企图在线性时间里贪心解出来。这个思路听着很省事但稍微构造一个反例就崩了。假设text1 abcdetext2 ace双指针从左往右扫匹配到a之后在text2里继续找c在text1里要跳过b看起来没什么问题。但如果两个字符串是ace和adcbe双指针扫到第一个字符a都匹配了接着text2要匹配c在text1里扫到c之前的d可以跳过然后匹配上c和e结果似乎也行。真正的反例是那种需要“放弃眼前匹配、留机会给后面更长匹配”的情况。比如text1 abcdtext2 acbd。双指针匹配到a后接下来text1是btext2是c这时候你要决定跳过谁的字符跳过text2的c去匹配后面的b会得到a b d如果不跳过c等text1走到c时匹配但后面text1的b已经错过了会得到a c d。贪心策略对“跳谁”的判断是局部的一旦选错全局答案就错了。而 LCS 要求的是全局最优这种“看起来当前可以推进但推进后反而拿不到更优结果”的场景恰恰是贪心解决不了的。1.2 为什么二维 DP 能覆盖所有“跳过”策略二维 DP 的核心思路是不直接构造子序列而是记录“两个字符串各自处理到某个前缀时能得到的公共子序列长度”。它把每个字符都当成“可选可不选”的独立决策然后在所有决策组合里取最优。dp[i][j]存的其实是text1前 i 个字符和text2前 j 个字符的 LCS 长度它天然包含了“跳过当前字符”的可能因为我在算dp[i][j]时可以选择只看dp[i-1][j]或dp[i][j-1]这两种做法分别代表“忽略text1[i-1]”和“忽略text2[j-1]”。这就是为什么 DP 比双指针稳健双指针每次只走单一路径DP 则是在一张表上同时维护所有子问题的结果最终答案由所有可能路径的最大值决定。2. 从暴力递归到动态规划一步步推导状态转移很多教程上来就给你dp[i][j]的递推公式但如果不理解这个公式从哪来代码隔两天就忘了。最稳妥的理解方式是从递归开始我先把问题的所有决策空间拆开。设计递归函数lcs(i, j)它表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度。注意这里用“前 i 个字符、前 j 个字符”来描述是为了后续对应到二维数组的下标。递归的终止条件很直观只要有一个字符串长度为 0公共子序列长度为 0直接返回 0。然后分两种情况讨论如果text1[i-1] text2[j-1]说明当前这两个字符可以成为公共子序列的一部分。既然它们相等就顺手把它们放进公共子序列里然后继续往前看lcs(i-1, j-1) 1。如果text1[i-1] ! text2[j-1]当前两个字符无法配对。此时有两种选择要么忽略text1的最后一个字符看lcs(i-1, j)要么忽略text2的最后一个字符看lcs(i, j-1)。取两者较大值作为结果。这个递归天然覆盖了所有情况两个字符相等时可以直接选不等时二选一跳过不会遗漏任何组合。用 Python 写出来def lcs_recursive(text1: str, text2: str) - int: m, n len(text1), len(text2) def dfs(i, j): if i 0 or j 0: return 0 if text1[i - 1] text2[j - 1]: return dfs(i - 1, j - 1) 1 else: return max(dfs(i - 1, j), dfs(i, j - 1)) return dfs(m, n)这段代码逻辑正确但时间复杂度是指数级的。因为每次不等时都会分叉成两个子问题dfs(i-1, j)和dfs(i, j-1)还会重复计算大量重叠的中间状态。你拿一个长度 20 的字符串去跑可能要等半天完全没法用。我刚开始学 DP 时的一个习惯是先写递归再把递归改成带备忘录的版本。带备忘录的递归其实就是自顶向下的 DP时间和二维循环一个量级但代码里保留了递归语义更容易验证逻辑是否正确。def lcs_memo(text1: str, text2: str) - int: m, n len(text1), len(text2) memo [[-1] * (n 1) for _ in range(m 1)] def dfs(i, j): if i 0 or j 0: return 0 if memo[i][j] ! -1: return memo[i][j] if text1[i - 1] text2[j - 1]: memo[i][j] dfs(i - 1, j - 1) 1 else: memo[i][j] max(dfs(i - 1, j), dfs(i, j - 1)) return memo[i][j] return dfs(m, n)这里memo[i][j]存的就是“前 i 个字符和前 j 个字符的 LCS 长度”所有状态只计算一次每个状态的计算时间是 O(1)整体复杂度降到 O(mn)。到了这一步再改成自底向上的二维数组遍历就非常自然了因为备忘录版本和表格版本填的是同一张表。2.1 从备忘录版本到自底向上填表到底改了什么备忘录版本是“用到哪个状态就现算哪个算完存起来”。自底向上版本则是“从最小的子问题开始把所有状态按依赖顺序全部算一遍”。依赖顺序怎么确定观察递推式dp[i][j] dp[i-1][j-1] 1依赖左上角dp[i][j] max(dp[i-1][j], dp[i][j-1])依赖上方和左方不管是哪条路dp[i][j]只和i-1行、j-1列的状态有关。所以只要按行从上到下、每行从左到右遍历计算dp[i][j]时它依赖的dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]都已经算好了。这也是动态规划里最常用的处理思路先写递归找到状态定义和转移关系再根据依赖方向确定遍历顺序最后用循环把表填出来。熟练之后你可以跳过递归直接写循环但新手阶段建议至少把递归逻辑推一遍能帮你在写转移方程时保持清醒。3. 二维 DP 的代码实现与手推表格到这一步直接写出二维 DP 的代码就顺理成章了。def longestCommonSubsequence(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]为什么dp数组是(m1) x (n1)而不是m x n因为我们需要单独留一行一列用来表示“空字符串”的情况也就是下标为 0 的行和列它们全部初始化为 0。这样处理之后text1[i-1]和text2[j-1]的下标映射就不会越界代码写起来也更干净。还有一个很隐蔽但很重要的细节当dp数组只有 0 行和 0 列是 0 时为什么不用对整张表做初始化因为其他格子都是待计算状态只要按顺序遍历遍历到dp[i][j]时它依赖的格子已经更新完毕不需要额外设置默认值。3.1 手推一遍表格彻底理解每格数字的含义空说理论不够直观我们用一个具体例子跑一遍text1 abcdetext2 ace。这个例子刻意选了长度不同的两个字符串能看出表中行和列是不对称的。初始状态第 0 行和第 0 列全部为 0表示任意字符串和空字符串的 LCS 长度为 0dpace0000a0b0c0d0e0开始遍历i1即text1第一个字符aj1text2[j-1]a和a相等所以dp[1][1] dp[0][0] 1 1。j2text2[j-1]c和a不相等dp[1][2] max(dp[0][2], dp[1][1]) max(0, 1) 1。这个 1 的含义是a和ac的 LCS 长度为 1。j3text2[j-1]e和a不相等dp[1][3] max(dp[0][3], dp[1][2]) max(0, 1) 1。第一行填完dpace0000a0111b0这里有一个值得品味的点dp[1][2]虽然是a和ac的结果但因为c没匹配上LCS 仍然是 1并没有因为多看了text2的一个字符而增加。这说明 LCS 长度是单调不减的dp[i][j] dp[i][j-1]恒成立。继续i2text1第二个字符bj1b ! adp[2][1] max(dp[1][1], dp[2][0]) max(1, 0) 1。j2b ! cdp[2][2] max(dp[1][2], dp[2][1]) max(1, 1) 1。j3b ! edp[2][3] max(dp[1][3], dp[2][2]) max(1, 1) 1。第二行填完dpace0000a0111b0111c0b的出现没有让任何位置的 LCS 变长原因是text2里没有b。所以整行都继承了上一行对应位置的最大值。这其实也是一条规律当text1新增的字符在text2里不存在时当前行所有dp值等于上一行。i3text1第三个字符cj1c ! adp[3][1] max(dp[2][1], dp[3][0]) max(1, 0) 1。j2c cdp[3][2] dp[2][1] 1 2。到这里abc和ac的 LCS 变成了 2对应子序列ac。j3c ! edp[3][3] max(dp[2][3], dp[3][2]) max(1, 2) 2。第三行填完dpace0000a0111b0111c0122d0text1走到c时终于和text2的第二个字符匹配上了dp值从 1 跳到 2。注意这个 2 来自dp[2][1] 1而不是dp[2][2] 1因为c只能接在ab和a的 LCS 之后而ab和a的 LCS 长度是 1加当前匹配的c变成 2。继续i4字符d情况跟b类似text2里没有d所以整行继承上一行dpace0000a0111b0111c0122d0122i5字符e关键的一行j1e ! adp[5][1] max(dp[4][1], dp[5][0]) max(1, 0) 1。j2e ! cdp[5][2] max(dp[4][2], dp[5][1]) max(2, 1) 2。j3e edp[5][3] dp[4][2] 1 3。最终表是这样dpace0000a0111b0111c0122d0122e0123答案dp[5][3] 3也就是abcde和ace的最长公共子序列是ace长度为 3。这张表本身也是一个很强的验证工具如果你以后在面试里写二维 DP可以用这种小例子快速自测表和代码对得上逻辑基本就稳了。3.2 二维 DP 的时间和空间复杂度两个循环分别遍历text1和text2所以时间复杂度是 O(mn)。空间上维护了一张(m1) x (n1)的表也是 O(mn)。当 m 和 n 都不大几百以内时这个复杂度完全没问题。但 LeetCode 上text1.length和text2.length最大可以到 10001000 x 1000的二维数组已经要占用约 1MB 内存如果将来面试官追问“能不能把空间降下来”就需要做滚动数组优化了。4. 空间优化到 O(n)滚动数组的两个隐藏陷阱这是面试里最容易翻车的一步。很多人能一口气写出二维 DP但一优化就踩坑主要是没搞明白“上一行的值”什么时候会丢。观察转移方程dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。也就是说当前行只用得到上一行和当前行左侧的数据再早的行根本不会再被用到。既然这样我们没必要保存完整的二维表只保留一行边算边覆盖。一维数组dp[j]在进入第i轮循环之前表示上一行第 j 列的结果在更新过程中dp[j]会逐步被覆盖成当前行的结果。问题来了当计算dp[j]时既需要旧的dp[j-1]当前行左侧已经更新过又需要旧dp[j]上一行同列还没更新还需要左上角的dp[j-1]的旧值也就是上一行 j-1 列的值但这个值在更新dp[j-1]时已经被覆盖了。于是我们需要一个额外变量pre来保存“左上角”的旧值。def longestCommonSubsequence_optimized(text1: str, text2: str) - int: m, n len(text1), len(text2) dp [0] * (n 1) for i in range(1, m 1): pre 0 # dp[i-1][0]其实始终为 0 for j in range(1, n 1): temp dp[j] # 先保存旧 dp[j]即上一行的 dp[i-1][j] if text1[i - 1] text2[j - 1]: dp[j] pre 1 else: dp[j] max(dp[j], dp[j - 1]) pre temp # 把旧 dp[j] 留给下一个 j 作为“左上角” return dp[n]这段代码初看容易绕建议配合注释读三遍。核心在temp dp[j]和pre temp这两行pre永远存的是“当前j的左上角”也就是上一轮循环中旧的dp[j-1]。当我们执行pre temp时temp是这一轮j开始时的旧的dp[j]等到下一轮j1时它正好是上一行的第 j 列也就是dp[i-1][j]此时它就成了计算dp[j1]时需要的左上角值。4.1 这个优化里最常见的两个错误第一个错误是忘记保存pre。如果你直接写for j in range(1, n 1): if text1[i-1] text2[j-1]: dp[j] dp[j-1] 1 # 错误dp[j-1] 已经是当前行的值了这样用到的dp[j-1]是当前行更新过的值而我们需要的是上一行的dp[j-1]。一旦当前行列的值还没正确填充结果就错了。第二个错误是内层循环的方向。如果从右往左遍历dp[j-1]反而是旧值但pre的维护方向就不同了思路容易乱。我更建议固定从左到右配pre变量因为这种写法逻辑最直观面试时也最容易讲清楚。4.2 还能再省吗可以把text1和text2对调滚动数组的空间是 O(n)其中 n 是第二个字符串的长度。如果 m 和 n 差距很大比如一个字符串长度 1000另一个长度 100我们可以先在代码里把较短的字符串放在内层循环这样空间占用就是 O(min(m, n))进一步省内存。def longestCommonSubsequence_final(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): pre 0 for j in range(1, n 1): temp dp[j] if text1[i - 1] text2[j - 1]: dp[j] pre 1 else: dp[j] max(dp[j], dp[j - 1]) pre temp return dp[n]这里对调的意义不只是“代码更优雅”而是实打实的内存优化。假设text1是 10000 个字符text2是 100 个字符对调后数组长度从 10001 变成 101差距很可观。刷题的人可能感受不深但如果在真实项目里处理很长的序列这种细节值得留意。5. 进阶需求不只返回长度要打印最长公共子序列本身LeetCode 原题只要求返回长度但面试官很爱追问一句“能不能把这个子序列本身打印出来”毕竟真实业务里长度往往不直接解决问题我们要的是具体的差异内容。打印的思路是从dp表右下角开始回溯。如果要用一维数组回溯就得额外保存转移方向通常还是得回退到二维表或者用二维数组存转移路径。最简单的方案是直接用二维 DP计算时同时记录“每个格子是从哪个方向来的”最后逆推整个路径。记录转移方向可以用一个小技巧在填充dp[i][j]的时候如果当前字符相等它的来源是左上角dp[i-1][j-1]如果不等来源是上方dp[i-1][j]和左方dp[i][j-1]中较大的那个。为了节省空间也可以在回溯时重新比较text1[i-1]和text2[j-1]以及dp[i-1][j]和dp[i][j-1]的大小来判断方向不需要额外数组。回溯打印的代码如下def print_lcs(text1: str, text2: str) - str: 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]) result [] i, j m, n while i 0 and j 0: if text1[i - 1] text2[j - 1]: result.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(result))这段代码的判定逻辑要仔细想当text1[i-1] ! text2[j-1]时dp[i][j]要么来自上方要么来自左方。如果dp[i-1][j] dp[i][j-1]说明上方的值更大当前格子继承了上方所以向上走i - 1否则向左走j - 1。两边相等时往哪边走都行不妨统一向左。用我们之前的例子text1 abcde、text2 ace验证起点i5, j3text1[4]e等于text2[2]e加入e移动到(4, 2)。text1[3]d不等于text2[1]c比较dp[3][2]2和dp[4][1]1上方更大向上走到(3, 2)。text1[2]c等于text2[1]c加入c移动到(2, 1)。text1[1]b不等于text2[0]a比较dp[1][1]1和dp[2][0]0上方更大向上走到(1, 1)。text1[0]a等于text2[0]a加入a移动到(0, 0)结束。result逆序后是ace正确。实现打印时有两个容易出错的地方第一个是拼接顺序。回溯是从尾部往前找的所以result列表里是倒序的最后记得reversed或反转。第二个是当text1[i-1] ! text2[j-1]时要避免两边都走。用elif dp[i-1][j] dp[i][j-1]判断如果相等就走默认方向避免死循环。5.1 如果有多个最长公共子序列这个打印方法输出哪个当dp[i-1][j] dp[i][j-1]时说明当前格子有两个最大来源我们代码里默认向左走。这会导致打印出的子序列是“按字典序比较偏向左/偏靠后”的那一条但长度一定是对的。如果你需要输出所有 LCS那就要把回溯改成搜索用集合存储所有可能路径复杂度会指数上升一般面试不会追问到这个深度但心里要有数。不做这个优化的话打印版代码的复杂度和二维 DP 一致都是 O(mn) 时间、O(mn) 空间。如果面试官既要求打印又要求 O(n) 空间可以额外加一个二维数组记录方向但空间又回去了或者直接用 Hirschberg 算法做线性空间回溯不过这个太进阶大多数场景用不上。6. LCS 的变体题和在真实场景中的用处LCS 不只是面试题它背后的思想在很多场景都有直接应用。我整理了 4 个最常碰到的关联内容从刷题角度和工程角度各说几个。6.1 最长回文子序列把 LCS 用起来的经典套路LeetCode 516「最长回文子序列」可以转换成 LCS 来做把原串s反转成rev_s然后求s和rev_s的 LCS 长度。因为回文串从左读和从右读一样所以它的正序版本一定同时出现在s和rev_s中两个字符串的最长公共子序列就是最长回文子序列。这个转换虽然简洁但有一个坑如果只要求长度这个转换是绝对正确的但如果要打印具体回文串用 LCS 解出来的结果不一定是合法回文因为可能同时取了原串同一位置的字符。稳妥起见打印回文子序列时还是用区间 DP状态定义为dp[i][j]表示s[i..j]的最长回文子序列长度。这也是为什么很多题解里回文子序列题目单独开了个区间 DP 专题。6.2 编辑距离LCS 的“加操作”版LeetCode 72「编辑距离」是 LCS 最亲近的变体之一。编辑距离允许三种操作插入、删除、替换要求把word1变成word2的最小操作次数。它的状态转移和 LCS 有很多相似之处如果word1[i-1] word2[j-1]不需要额外操作dp[i][j] dp[i-1][j-1]。如果不等有三种选择删掉word1[i-1]dp[i-1][j] 1、在word1插入一个字符对应word2[j-1]dp[i][j-1] 1、把word1[i-1]替换成word2[j-1]dp[i-1][j-1] 1三者取最小。对比之后你会发现LCS 的状态转移是“相等就加一不等就取 max”编辑距离是“相等就继承不等就取 min 并加一”。一个是求最长公共长度一个是求最短编辑代价框架几乎同一套。我建议刷完 LCS 之后立刻刷编辑距离两个一起做DP 的字符串类问题基本就通了。6.3 工程里真正用到 LCS 的地方很多同学会觉得 LCS 是纯算法题和业务无关。实际上我在做代码比对和配置 diff 时遇到过不少类似需求。最典型的是git diff背后的核心算法。虽然 Git 实际上用的是 Myers diff 算法但 Myers 的很多思想和 LCS 高度相关本质都是在找两个序列之间最小的编辑路径。当你git diff看到一堆和-时背后就是这类动态规划在做匹配。另一个典型场景是日志比对。线上服务出现异常时我经常拿正常日志和异常日志做对比通过最长公共子序列找出两者相同的部分快速定位到哪一行日志开始出现差异。自己写的 log 比对脚本如果只是逐行 diff遇到大量相同前缀会浪费很多空间用 LCS 可以一次性找出所有相同片段。还有文本查重和代码相似度检测。把两段代码先做分词或按行拆分然后求 LCS长度占各自行数的比例可以作为一个相似度指标。当然实际工程里会配合哈希去重和向量化但 LCS 是理解这类问题的基石。6.4 如果输入串很长还有什么优化思路当 m、n 都到 10^5 量级时O(mn) 时间会爆掉这时候需要上“最长公共子序列的贪心二分优化”算法可以把时间复杂度优化到 O((mn) log n) 级别。核心思路是把 LCS 转化成“最长递增子序列”问题遍历第一个字符串记录每个字符在第二个字符串里出现的位置降序排列然后拼接成一个数组求这个数组的最长递增子序列长度。但这个方法只适用于字符集有限的场景比如小写字母如果字符集很大或者字符串里有重复字符很多效果会打折扣。面试一般不会主动考这种优化但你可以提一句作为扩展显得对边界情况有意识。7. 我对这道题的一点个人体会刷到第 49 天我越来越觉得动态规划题不能靠背模板关键是“从递归到递推”的推导过程。LCS 作为二维 DP 的入门题好处是状态定义和转移方程非常干净没有贪心策略的弯弯绕绕很适合用来练习分析子问题的能力。我当时的刷法是这样的第一遍自己写带备忘录的递归版本保证思路正确第二遍改成二维循环用一个小例子手推 dp 表第三遍做空间优化在原代码上改成滚动数组最后试着把子序列打印出来。四遍下来这道题的每一个细节都记得很牢再去做编辑距离、两个字符串的删除操作明显顺畅了很多。如果你也在刷 DP建议别急着看题解先拿出纸笔画一画哪怕推错了也比直接看答案有价值。把这道题真正吃透你收获的不只是一个题解而是一整类字符串动态规划问题的解题路径。