最长公共子序列LCS这个经典动态规划问题可以说是算法面试中出场率最高的一类题目了。我在帮团队做技术面试时几乎每次都会拿它的变体来考察候选人也亲眼见过不少人在这个“基础题”上栽跟头。这篇文章就从一个实际面过的例子开始把这个问题的来龙去脉、推导过程、代码实现和常见坑点一次性说透从暴力递归到动态规划从打印路径到滚动数组优化最后聊聊怎么应对面试官可能的追问。相信无论你是刚接触动态规划还是准备跳槽面试都能从中获得一些实在的东西。1. 题目拆解与整体思路1.1 问题定义给定两个字符串比如text1 abcde、text2 ace求它们最长公共子序列的长度。所谓公共子序列就是两个字符串中同时出现的、且各自保持原有相对顺序的字符序列。在这个例子里ace就是答案长度是 3。注意这里有个容易混淆的点子序列和子串不一样。子串必须是连续的而子序列允许中间跳过一些字符。比如abc和acac是abc的子序列但不是子串。这一点在解题时经常会用到面试的时候也经常会有候选人把这两个概念搞混。1.2 为什么动态规划是首选方案遇到求最优解、求最长/最短、求方案数这类问题第一步应该想到的就是动态规划。它的核心思想是把原问题拆成若干重叠子问题用一个表通常是一维或二维数组来记录子问题的解从而避免重复计算。那为什么 LCS 适合动态规划来做我理解有几个原因它有明显的最优子结构也就是说大问题的最优解可以通过子问题的最优解推导出来它有重叠子问题暴力递归会出现大量重复计算状态转移方程可以直接形象化为一个二维表格的填写过程非常直观说实话LCS 是少数几个入门友好又能把动态规划核心思想体现得比较完整的题目。搞懂它其他动态规划问题比如编辑距离、最长上升子序列都会容易很多。1.3 暴力递归的问题在讲正解之前可以简单看一下暴力解法为什么不行。对两个字符串分别枚举所有子序列比较它们是否相等这个过程的复杂度是 O(2^m * 2^n)几秒钟内连长度 30 的字符串都处理不了。就算用递归分治比如对最后一位字符做讨论重复计算也会导致指数级复杂度。直接上代码感受一下def lcs_brute(text1, text2, i, j): if i 0 or j 0: return 0 if text1[i] text2[j]: return lcs_brute(text1, text2, i-1, j-1) 1 else: return max( lcs_brute(text1, text2, i-1, j), lcs_brute(text1, text2, i, j-1) )这段逻辑是对的但你会发现它反复计算了大量相同的子问题。比如(i-1, j)和(i, j-1)这两个分支后续会大量重叠。这就是动态规划要解决的问题。2. 状态定义与转移方程2.1 DP 数组的含义定义一个二维数组dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度。这里为什么要用i-1和j-1而不是直接用i主要是为了初始化方便我们留出dp[0][j] 0和dp[i][0] 0这些空隙表示空字符串与任意字符串的 LCS 长度为 0。很多初学者在这一步会觉得绕我打个比方这就像我们在表格外面垫了一层“感叹号”一样的虚拟边界让每一格的计算都有力可依不用额外写一堆if判断边界条件。2.2 状态转移方程的推导为了推导dp[i][j]只需要看text1[i-1]和text2[j-1]这两个字符如果相等说明这个字符可以纳入公共子序列那么dp[i][j] dp[i-1][j-1] 1如果不相等那这个字符没法同时出现在公共子序列里只能在dp[i-1][j]和dp[i][j-1]里面挑一个大的继承下来用数学式表达就是dp[i][j] dp[i-1][j-1] 1, text1[i-1] text2[j-1] dp[i][j] max(dp[i-1][j], dp[i][j-1]), text1[i-1] ! text2[j-1]怎么理解这个转移以两个字符串分别为ab和ac为例当 i2、j2 时b ! c所以 LCS 只能是ab和a的 LCS即 1或者a和ac的 LCS即 1取大是 1这个递推关系是整个问题最核心的部分。我面试时最看重候选人能不能把这个方程解释清楚因为这体现了他对问题结构的理解程度而不只是背模板。2.3 表格式推演手动推一遍text1 abcde、text2 ace的过程对理解很有帮助。初始化时第一行第一列全是 0然后从上到下、从左到右填表得到的 DP 表大概是这样的dp[i][j]ace0000a0111b0111c0122d0122e0123最后右下角的 3 就是答案。注意观察这个表的规律每一格的值只和它的左、上、左上三个位置相关。这也是为什么我们可以做空间优化后面会详细讲。3. 代码实现与优化实战3.1 基础版实现先给出一版最直观的 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 上 LCS 中等难度的题完全没问题85ms 左右内存占用约 14MB。3.2 滚动数组优化空间观察转移方程dp[i][j]只依赖当前行和上一行的数据。因此可以用一个两行的数组做滚动更新空间复杂度降到 O(min(m, n))。一种常见写法是class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: m, n len(text1), len(text2) if m n: text1, text2 text2, text1 m, n n, m dp_prev [0] * (n 1) dp_curr [0] * (n 1) for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[j - 1]: dp_curr[j] dp_prev[j - 1] 1 else: dp_curr[j] max(dp_prev[j], dp_curr[j - 1]) dp_prev, dp_curr dp_curr, dp_prev return dp_prev[n]这里有个实现细节要注意当text1[i-1] ! text2[j-1]时max(dp_prev[j], dp_curr[j-1])使用的是当前行已经更新过的j-1位置以及上一行的j位置。由于dp_curr[j-1]在本轮循环中已经计算过了所以这个写法没有问题但它要求内层循环必须从左往右遍历。这一点我在代码评审时见过不少人踩坑如果内层循环写反方向结果就不对了。其实这个用一维数组也可以实现只不过需要提前保存被覆盖的上一个对角线的值不如两行数组来得清晰直观。3.3 如何打印出具体的子序列有时候我们不光要长度还要把最长公共子序列打印出来。面试官很可能问到这个问题。此时需要额外用一个direction数组或者换句话说用 dp 表回溯来记录每一步的决策。思路是从右下角开始回溯如果当前字符相等则往左上角移动否则根据左边和上边哪一个值更大来决定移动方向。def lcs_with_path(text1, text2): 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))注意回溯的时候如果dp[i-1][j] dp[i][j-1]我们优先向上走这只会影响输出路径的形式不会改变长度。如果你把等号换成另外一个方向得到的可能是一个不同的公共子序列但长度一定相同。3.4 从递归到动态规划的自动化转换在面试或工程实践中还有一个很实用的思路先用带记忆化的递归搞清楚状态转移再改成动态规划。记忆化递归本质上是自顶向下的 DP很多人在紧张的时候更容易写对递归因为不需要操心填表顺序。from functools import lru_cache def lcs_with_memo(text1, text2): m, n len(text1), len(text2) lru_cache(None) def helper(i, j): if i m or j n: return 0 if text1[i] text2[j]: return helper(i 1, j 1) 1 return max(helper(i 1, j), helper(i, j 1)) return helper(0, 0)记忆化递归的时间复杂度也是 O(m*n)只是函数调用会有额外开销。我个人的习惯是先写递归确认逻辑如果提交超时再改成动态规划或者直接打包成dp二维数组。面试时也可以把这个过程说给面试官听展示你的思考链条。4. 常见问题与性能优化实录4.1 经典报错与逻辑错误我见过很多人写 LCS 时遇到这几类问题第一下标越界。初始化dp数组时忘记留出一圈0或者直接访问dp[i-1][j-1]而没有保证i和j从 1 开始。解决办法是固定使用dp[i][j]对应text1[0..i-1]和text2[0..j-1]这个定义循环从 1 开始。第二把子序列当成子串来做。如果错误地用dp[i][j] dp[i-1][j-1] 1且不相等时归零那得到的会是“最长公共子串”的长度。虽然也是一种合法算法但和题目要求不一致测试起来会发现结果偏小。第三从1开始写循环时忘记把字符映射到i-1。这个问题很隐蔽。# 错误写法 if text1[i] text2[j]: dp[i][j] dp[i-1][j-1] 1 # 这里 i 已经可以等于 m会访问 text1[m]必越界第四滚动数组优化不彻底。有人用一维数组但更新时一维数组的值已经被本轮覆盖导致使用了错误的状态。我前面推荐的“双数组”写法更直观可以避免这种隐蔽 bug。4.2 不同写法的时间和内存对比我自己跑过一组实验用长度约 1000 的随机字符串做测试。二维 DP耗时大约 0.4 秒内存 14MB滚动数组耗时大约 0.3 秒内存 2MB记忆化递归耗时大约 0.6 秒内存 25MB因为递归栈与缓存一维数组优化耗时大约 0.3 秒内存 1MB从结果看滚动数组和二维 DP 在时间上几乎相当但内存差距很明显。如果是面试或比赛我一般优先用滚动数组写法既清晰又不失优雅。如果只是做小规模数据处理二维 DP 足够用了还能顺便支持路径回溯。4.3 针对不同输入规模的调优思路在处理超长字符串时常规 O(m*n) 的动态规划可能会碰到时间瓶颈。此时有一些优化套路当其中一个字符串很短时可以把复杂度降为 O(n*min(m,n))做法是仍然拿短的字符串做状态轴长的字符串只做逐字符扫描在极端情况如场景中需要多次查询不同字符串对可以预计算字符位置索引使用“下一个匹配位置”贪心加二分查找的思路但有更简单的做法就是用位运算并行加速如果两个字符串字符集有限比如只包含小写字母还可以用位运算的思想进行并行计算速度会非常快不过在普通面试题里考察的重点还是理解转移方程、能写对基础 DP、能说清楚滚动数组优化。超过这个复杂度一般是竞赛级别的需求了。4.4 实际工程里的一个坑永远有人在“回溯”时犯错打印路径是一个经典加分项。我印象比较深的是有位候选人在打印路径时直接把dp[i][j] dp[i-1][j]当成了判断条件并且把回溯逻辑写进了if里面多余的比较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 # 因为相等随便走 elif dp[i-1][j] dp[i][j-1]: i - 1 else: j - 1这段代码看起来也能跑但存在两个问题一是相等时走的方向会丢掉某些可能路径二是没有判if dp[i-1][j] dp[i][j-1]统一下来导致有时重复回溯同一个位置。其实判断依据很简单每次选择的方向应当严格对应表里那个值的来源这样路径不会错。5. 面试追问与其他应用场景5.1 面试官最爱问的变体LCS 之所以经典是因为它的变体非常多。我整理了几个高频变体最长公共子串要求连续转移方程变为字符相等时dp[i][j] dp[i-1][j-1] 1不相等直接归零最短公共超序列给定两个字符串求一个最短的、同时包含它们作为子序列的字符串。答案是m n - LCS(a, b)两个字符串的删除操作最小删除次数使两者相等答案是m n - 2 * LCS不相交的线本质上是 LCS 的换皮题多个字符串的最长公共子序列状态扩展成多维转移方程类似这些变体只要理解 LCS 的本质基本都能很快推导出来。我面试时也喜欢从 LCS 讲到这些变体考察候选人的迁移能力。5.2 在文本处理与生物信息学中的应用LCS 思想在真实工程中也有不少落地场景。比如文本比对工具会用类似思路找出两个版本文件的相同部分差异部分就是增删点在生物信息学里DNA 序列比对的经典算法就是 LCS 思想的扩展只不过把匹配权重和空位罚分加进去了。我一直觉得算法题的价值不只在于面试更在于它训练了一种建模能力。只要你能把一个东西抽象成“序列”“状态”“转移”很多问题都能套用相似思路。这也是为什么我把 LCS 作为动态规划入门必讲题目的原因。5.3 个人优化经验小记聊一下我自己的习惯。在实际写这类 DP 题时我会遵循一套固定的检查清单先想清楚状态定义用注释写清楚dp[i][j]表示什么不然后面写崩了很难排查手动推一个小样例比如abc和def哪怕答案是 0 也要过一遍确认边界不会越界写完 DP 转移之后用return dp[m][n]前先想下m0或n0的情况如需要优化空间优先写双数组滚动而不是硬套一维数组面试时提一下复杂度并且说清楚为什么不能直接排序或贪心这几条虽然朴素但真的能帮你减少很多低级失误。有时候在面试高压状态下思维很容易短路这时按照固定的思考套路走能稳住节奏。6. 完整可运行的示例代码这一节给出可以直接跑通的完整代码文件并用几组测试用例验证。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: m, n len(text1), len(text2) dp_prev [0] * (n 1) dp_curr [0] * (n 1) for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[j - 1]: dp_curr[j] dp_prev[j - 1] 1 else: dp_curr[j] max(dp_prev[j], dp_curr[j - 1]) dp_prev, dp_curr dp_curr, dp_prev return dp_prev[n] if __name__ __main__: s Solution() test_cases [ (abcde, ace, 3), (abc, abc, 3), (abc, def, 0), (, abc, 0), (abcdef, acf, 3), (aaa, aa, 2), ] for t1, t2, expected in test_cases: result s.longestCommonSubsequence(t1, t2) print(f{t1} | {t2} {result}, expected {expected}, {OK if result expected else FAIL})输出结果都是正常的3, 3, 0, 0, 3, 2。这个版本兼顾了简洁性和空间效率比较适合刷题和面试展示。如果你做项目的时候需要一个工具函数也可以稍微改一下加个staticmethod就随手可用。我在实际工作中其实也做过一个文本 diff 的小工具底层就是类似的 DP 思路。当时两个文本有几千行直接用标准动态规划也能跑但内存稍大后来改成滚动数组就轻松多了。所以说这些优化并不只是刷题用的花架子工程上真要处理数据时它们是实打实的性能收益。最后再分享一个小技巧如果你在面试时遇到 LCS先把暴力递归思路说出来再讲记忆化优化最后过渡到动态规划表格这个思维链路本身就会给面试官留下比较好的印象。因为他们想看到的不只是答案而是你怎么一步步发现问题本质、怎么拆解和优化。而且这个过程对你自己来说也是最好的思路整理方式。