最长公共子序列这道题在算法动态规划的题单里刷脸频率极高。LeetCode 1143题目编号很靠前几乎所有准备面试的开发者都会在某个时间点撞上它。我第一次刷这道题时照着题解抄了一遍二维DP看着状态转移方程好像懂了但第二天让我自己写手又僵了。后来认真把“dp[i][j]到底代表什么”“为什么相等分支只需要看左上方”“为什么滚动数组能省空间”这几个问题逐个啃透才敢说真正掌握了这道题。这篇博文就围绕LeetCode 1143展开从问题本质、状态定义、转移方程推导、代码实现到空间优化、常见坑点以及高频变体题把最长公共子序列讲透。适合正在学动态规划的初学者也适合准备笔试面试、想快速过一遍LCS相关题型的开发者。内容不玩虚的全部是我实际刷题和给身边的人讲题时沉淀下来的一套理解路径。1. 先把问题和“子序列”三个字掰清楚开始之前先确认一件事情什么是子序列题目里说的是text1和text2两个字符串找它们的最长公共子序列长度。这里的子序列不要求字符连续只要保持原顺序即可。举个例子text1 abcdetext2 ace。公共子序列可以是a、c、e、ae也可以是ace。其中ace最长长度为3所以答案就是3。注意abcde里a在第1位c在第3位e在第5位它们不需要挨在一起只需要保证在text1和text2中各自都是按顺序出现的。1.1 子序列和子串一字之差天壤之别面试里经常有人把子序列和子串搞混这是基础概念必须拿捏清楚。子串原字符串中连续的一段。子序列原字符串中按顺序挑出的字符不要求连续。生活化类比子串就像从一列火车里抽一节连续的车厢子序列则是从一列火车里按顺序挑几个人出来人不需要坐在相连的位置上。abcde的子串有ab、bc、de等它的子序列则有ae、bd、ace等。“bde”也是合法子序列因为它按b→d→e的顺序出现在原串中。这个区别直接决定了状态转移方程的写法。子串问题在字符不匹配时需要重新计数子序列问题因为有“跳过”的自由度转移方程要考虑“不选”的情况。LeetCode 1143之所以是动态规划入门的核心题正是因为它的状态设计思路能迁移到大量动规题型上。1.2 为什么贪心解决不了LCS拿到这类题第一反应往往是两个指针从前往后扫相同就匹配不同就跳。这不就完了吗我起初也这么想。尝试一个反例text1 abctext2 acb。从text1的a开始匹配text2的atext1的b尝试匹配text2的下一个字符c不匹配text2跳下一个b匹配成功text1的c继续找text2只有一个c但在b之前已经过去了匹配失败。贪心匹配得到的是ab长度2。但实际最长公共子序列是ac或ab长度也是2等一下虽然这个例子里贪心碰巧没输但你稍微改一下text1 abcdeftext2 abxdfe。贪心会尽量匹配前面的ab然后c在text2里找不到跳过d、e都匹配上了得到abde长度4。这没问题。再改text1 abcabtext2 aabb。贪心从左往右a匹配ab匹配a不匹配跳b匹配b得到ab然后text1的c跳过a找不到可匹配的字符b匹配最后的b得abb长度3实际的最优应该是aabb长度4。贪心的短视在“选择哪个相同的字符进行匹配”时暴露了它不知道未来还有多少字符等着。所以结论就是LCS这类问题具备最优子结构但局部贪心选择不能保证全局最优。你必须在每个位置保留“可能的最优长度”让后续决策在这些候选之上继续生长这就是动态规划切入的时机。1.3 状态定义为什么不叫dp[i]而叫dp[i][j]一维DP解决的是单序列问题比如最长递增子序列。而LCS是双序列问题两个字符串的匹配情况互相影响必然要用二维状态。定义dp[i][j]为text1的前i个字符和text2的前j个字符的最长公共子序列长度。这个定义里有几个点要反复确认“前i个字符”是包含0到的dp[0][j]表示text1为空串和text2的前j个字符的LCS显然等于0。dp[i][j]不一定以第i个字符或第j个字符结尾它记录的是一个前缀范围内的最佳结果。最终答案是dp[m][n]即两个完整字符串的最长公共子序列长度。很多新手的误区是把dp[i][j]定义成“以text1[i]和text2[j]结尾的LCS长度”。这个定义会导致转移方程极其别扭因为公共子序列不一定以两个字符串的某对相同字符结尾你还要额外维护一个全局最大值。而“前缀”式定义天然包含了全局信息是理解后续所有变体的根基。2. 状态转移方程从哪里来动态规划的核心不是记住方程而是能自己推导。题目做多了你会发现所有的二维DP都长得很像区别就在于“相等时怎么做不相等时怎么做”。2.1 从具体例子出发推演转移过程假设text1 abcdetext2 ace我们来看dp值是怎么填出来的。先初始化dp[i][0] 0dp[0][j] 0因为任何字符串和空串的公共子序列长度都是0。然后逐行填表i1text1[0]a。j1text2[0]a相等dp[1][1] dp[0][0] 1 1。j2text2[1]c不相等dp[1][2] max(dp[0][2], dp[1][1]) max(0, 1) 1。j3text2[2]e不相等dp[1][3] max(dp[0][3], dp[1][2]) max(0, 1) 1。i2text1[1]b。j1b vs a不相等dp[2][1] max(dp[1][1], dp[2][0]) max(1, 0) 1。j2b vs c不相等dp[2][2] max(dp[1][2], dp[2][1]) 1。j3b vs e不相等dp[2][3] max(dp[1][3], dp[2][2]) 1。i3text1[2]c。j1c vs a不相等dp[3][1] max(1, 0) 1。j2c vs c相等dp[3][2] dp[2][1] 1 2。j3c vs e不相等dp[3][3] max(dp[2][3], dp[3][2]) max(1, 2) 2。i4text1[3]d。j1不等dp[4][1] 1j2d vs c不等dp[4][2] max(dp[3][2], dp[4][1]) 2j3d vs e不等dp[4][3] max(dp[3][3], dp[4][2]) 2。i5text1[4]e。j1e vs a不等dp[5][1] 1j2e vs c不等dp[5][2] max(dp[4][2], dp[5][1]) 2j3e vs e相等dp[5][3] dp[4][2] 1 3。最终答案3和预期完全一致。把dp[i][j]的转移归纳成两条公式如果text1[i-1] text2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])注意代码里用的是i-1和j-1因为dp数组的第1位对应字符串的第0个字符这里存在一个索引偏移是初学者最容易写错的地方。2.2 为什么相等分支不需要比较另外两个方向很多人会有疑问两个字符相等时为什么不写成dp[i][j] max(dp[i-1][j-1] 1, dp[i-1][j], dp[i][j-1])万一不选这对相等的字符得到的结果更大呢答案是不会。这里有一条很重要的性质可以从逻辑上证明因为dp[i-1][j]表示text1前i-1个字符和text2前j个字符的LCS长度而dp[i-1][j-1]是text1前i-1个字符和text2前j-1个字符的LCS长度。多了一个字符text2[j-1]LCS长度要么不变要么增加1所以dp[i-1][j] dp[i-1][j-1]也就是说dp[i-1][j-1] 1 dp[i-1][j]不对这个不等式不成立因为dp[i-1][j-1] 1比dp[i-1][j]可能大也可能小。更严谨的证明思路是dp[i-1][j-1] dp[i-1][j] dp[i-1][j-1] 1。因为text2前j个字符比前j-1个字符最多多一个可匹配字符LCS长度最多增加1。同理dp[i-1][j-1] dp[i][j-1] dp[i-1][j-1] 1。所以当text1[i-1] text2[j-1]时我们可以在dp[i-1][j-1]的基础上把这对相同字符接上去得到dp[i-1][j-1] 1。这个值至少和dp[i-1][j]、dp[i][j-1]一样大或者说不会小于它们。因此直接用dp[i-1][j-1] 1即可不需要做三层max比较。这部分原理在面试时如果被追问能够讲清楚会非常有说服力。2.3 边界条件里藏着的小陷阱dp表的第0行和第0列全部初始化为0。这个初始化且只有这一步其余格子由转移方程自动填出。但有一个代码层面的坑值得单独说字符串的charAt索引和dp数组索引之间相差1。text1.charAt(i-1)对应的是dp[i]这一行的决策依据。如果直接用text1.charAt(i)去比较轻则漏掉最后一个字符重则数组越界。这种情况在面试白板编程时尤其容易发生我帮人review代码时见过太多次。3. 完整代码实现与空间优化理解了状态定义和转移方程写代码其实就剩最后一公里了。3.1 二维DP完整实现版以Python为例先用最直观的二维数组来实现def longestCommonSubsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) # dp[i][j] 表示 text1 前 i 个字符和 text2 前 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 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)使用了一个完整的二维数组。m和n分别是两个字符串的长度。LeetCode的测试数据最大在1000级别100万次操作完全能过。但如果两个字符串长度都是10000二维表就存不下了这时候要考虑空间优化。3.2 滚动数组优化把二维表压成一维数组观察转移方程dp[i][j]只依赖三个方向左上角dp[i-1][j-1]正上方dp[i-1][j]正左方dp[i][j-1]也就是说当前行只和上一行以及当前行左侧有关再往前的行的数据完全没必要保留。所以可以用一维数组滚动更新把空间从O(m×n)压缩到O(n)。实现时有一个关键点计算dp[j]时要用到左上角dp[i-1][j-1]但一维数组更新后上一行的dp[j-1]已经被当前行的值覆盖了。因此必须在覆盖之前先保存左上角的值。def longestCommonSubsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) # 空间优化只保留一行长度取 n1 dp [0] * (n 1) for i in range(1, m 1): prev 0 # 相当于 dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 先保存当前 dp[j]下一轮作为左上角使用 if text1[i - 1] text2[j - 1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j - 1]) prev temp return dp[n]这里的prev变量非常关键。一开始prev 0对应第i-1行的dp[0]也就是dp[i-1][0] 0。进入内层循环后当j1时如果字符相等dp[1] prev 1这里的prev就是dp[i-1][0]然后把temp也就是更新前的dp[1]即dp[i-1][1]保存为prev下一轮j2prev就是dp[i-1][1]正好是需要的左上角。这个技巧面试时写在白板上会加很多印象分。如果只写出二维DP也不会扣分但主动优化一版聊两句原理说明你真的理解这道题了。3.3 复杂度分析为什么空间可以进一步优化还有一种优化思路始终遍历较短的那个字符串作为内层循环让滚动数组的长度尽可能小。def longestCommonSubsequence(text1: str, text2: str) - int: # 如果 text2 更长交换确保内层数组较短 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): prev 0 for j in range(1, n 1): temp dp[j] if text1[i - 1] text2[j - 1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j - 1]) prev temp return dp[n]这不会改变时间复杂度但能进一步压空间常数。在极端场景下如果text2长度为1数组长度只有2空间开销几乎可以忽略。这种细节在实际工程里不常用但在算法竞赛或面试手撕环节是一个能体现功力的优化点。顺便补充一个工程化视角在真实业务里两个很长的文本做diffLCS只是中间步骤后续还要根据dp表回溯出具体的差异块。这时候空间优化就要谨慎因为回溯需要完整的二维dp表。面试如果只问长度滚动数组完美如果考官追问“那你能打印出最长公共子序列吗”就不能再用一维数组方案了得保留完整dp表。4. 常见问题与调试经验下面这些坑我见过身边的同事和一起刷题的朋友踩过很多次自己也栽过整理出来供参考。4.1 dp数组初始化易错点症状可能原因正确做法结果比预期大初始化时把dp[0][]或dp[][0]设置成了1任何字符串与空串的LCS长度都应为0结果少1比较字符时用了i和j而非i-1和j-1漏掉了首字符或尾字符统一用text1[i-1]与text2[j-1]比较相等时取了max(三个方向)试图用更保守的公式但没有理解相等时已经是最优相等时直接dp[i-1][j-1] 1记忆化递归超时递归函数没有缓存状态使用functools.lru_cache缓存二维状态或直接改迭代式DP这里重点说说第二行。假设text1 abctext2 a正确LCS长度为1。如果代码里图省事循环从i0, j0开始把dp[0][0]当初始状态比较的是text1[0]和text2[0]看似能算出1但一旦处理“text1第一个字符和text2最后一个字符匹配”的场景就会发生漏算或越界。老老实实从索引1开始遍历、让出第0行第0列作为边界是这套写法的定式。还有一点Python中初始化二维数组不要写成dp [[0] * (n 1)] * (m 1)这会创建m1个指向同一列表的引用。修改任意一行所有行一起变。我见过太多新手在这一行代码上debug半小时。正确写法是dp [[0] * (n 1) for _ in range(m 1)]或者用[[0] * (n 1)] * (m 1)的替代方案dp [[0 for _ in range(n 1)] for _ in range(m 1)]。4.2 谁动了我的最大值滚动数组debug实录有一次写滚动数组版本死活不对。字符相等时直接写dp[j] dp[j] 1结果有些用例偏大。原因就出在“加1”之前dp[j]已经被当前行左侧的更新影响了。正确的逻辑是相等时用上一行左上角的值加1而不是当前数组里的dp[j]自己加1。调试技巧是打印每一轮循环后的dp数组第1轮后: [0, 1, 1, 1] 第2轮后: [0, 1, 1, 1] 第3轮后: [0, 1, 2, 2] 第4轮后: [0, 1, 2, 2] 第5轮后: [0, 1, 2, 3]肉眼对比第3轮、第5轮的变化就能发现prev是不是保存对了。4.3 走出舒适区从“返回长度”升级到“输出具体子序列”如果面试官让打印出最长公共子序列本身该怎么办基于完整二维dp表从dp[m][n]开始倒推如果text1[i-1] text2[j-1]说明这个字符被匹配进来了加入结果序列向左上方移动i-1, 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]) res [] i, j m, n 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))如果题目要求所有公共子序列回溯时可以两边都走但结果数量可能指数级增长需要额外处理去重问题。这个属于竞赛级扩展面试极少考到。4.4 值得收藏的测试用例刷题时准备一组测试用例可以快速验证代码是否正确text1text2期望LCS长度说明0双空串abc0单空串abcabc3完全相等abcdef0完全不等abcdeace3经典示例abcacb2匹配顺序影响结果aaaaaa2重复字符边界abcdeffedcba1唯一匹配字符尤其最后一行两个字符串完全反向最长公共子序列长度为1很多人在这个用例上会把长度算成3因为“d、e、f在text1和text2里都有”。但没有一个字符在两个字符串中保持相同相对顺序的集合长度超过1。这种反向用例是检验状态转移理解的试金石。5. 变体题型与扩展思路同一个DP套路能延展出大量相关题目。面试中问LCS往往不是孤立的它会以各种变形出现。5.1 最长公共子串只要连续的部分把“子序列”改成“子串”约束变为字符必须连续。DP方程几乎是姊妹版dp[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][j] 0因为“连续”这个条件被打破了只能清零重新累积。最终答案是dp表中的最大值而不是dp[m][n]。对比LCS子序列允许断点所以不等时要取max延续之前的匹配子串不允许断点所以不等时直接清零。一个分支策略的不同就造成两种完全不同的题目。建议两个题一起刷效果翻倍。5.2 最长回文子序列LCS的间接应用题给定一个字符串s求它的最长回文子序列长度。很多人第一眼看不出来这和LCS有什么关系。解法把s反转得到rev(s)求s和rev(s)的最长公共子序列长度。为什么成立回文子序列从左往右读和从右往左读是一样的。那么它既是s的子序列也必然是rev(s)的子序列。反过来呢如果某个子序列同时出现在s和rev(s)中它是不是回文不一定但长度为LCS的公共子序列一定对应一个回文子序列详细证明可以看经典教材。这个转化思路在面试中非常常用它体现了“如何把未知问题归约到已知问题”的能力。5.3 最短公共超序列从LCS长度直接算出来给定两个字符串s1和s2找到一个最短的字符串使得s1和s2都是它的子序列。比如s1 abacs2 cab。最短公共超序列Shortest Common Supersequence, SCS长度可以直接用LCS算出来len(SCS) len(s1) len(s2) - len(LCS)重叠部分就是最长公共子序列。对s1abacs2cabLCS是ab或ac长度为2最短超序列长度为4 3 - 2 5。比如cabac长度5包含了abac和cab两个子序列。LCS的DP表还可以直接用来回溯SCS的具体内容属于“从一道题派生出一串题”的经典套路。5.4 LCS与编辑距离的关系编辑距离LeetCode 72是另一个著名的二维DP题它解决的是把s1变成s2需要的最少插入、删除、替换次数。编辑距离的DP思路和LCS有两个层面的相似都是双序列问题状态都定义为“前i个字符和前j个字符”。字符相等时直接继承对角线的结果不相等时LCS取max编辑距离取min加操作代价。区别在于目标不同LCS是找共同部分编辑距离是算转换成本。理解它们的相似与差异有助于建立DP的整体观。刷完1143再刷72会有一种“啊原来是同一套骨架”的顿悟感。我刷了这么多动态规划的题回头再看LeetCode 1143它最大的价值倒不是题本身而是它作为“双序列DP”的模板题把所有关键手法都集中在一个简单模型里前缀型状态定义、字符相等/不等的分支处理、滚动数组空间优化、二维表回溯解。这四个能力点几乎能覆盖大部分面试中的二维DP问题。建议不要背代码而是亲手画一次dp表用两个小字符串一步步填出来感受一下数字变化的规律。等你能不看任何参考资料从状态定义开始把整套推导完整写出来这道题才是真正过了。 
长河君 · 2026/10/20 11:46:54 · 阅读 1.2k LeetCode 1143最长公共子序列：动态规划从状态定义到滚动数组优化
最长公共子序列这道题在算法动态规划的题单里刷脸频率极高。LeetCode 1143题目编号很靠前几乎所有准备面试的开发者都会在某个时间点撞上它。我第一次刷这道题时照着题解抄了一遍二维DP看着状态转移方程好像懂了但第二天让我自己写手又僵了。后来认真把“dp[i][j]到底代表什么”“为什么相等分支只需要看左上方”“为什么滚动数组能省空间”这几个问题逐个啃透才敢说真正掌握了这道题。这篇博文就围绕LeetCode 1143展开从问题本质、状态定义、转移方程推导、代码实现到空间优化、常见坑点以及高频变体题把最长公共子序列讲透。适合正在学动态规划的初学者也适合准备笔试面试、想快速过一遍LCS相关题型的开发者。内容不玩虚的全部是我实际刷题和给身边的人讲题时沉淀下来的一套理解路径。1. 先把问题和“子序列”三个字掰清楚开始之前先确认一件事情什么是子序列题目里说的是text1和text2两个字符串找它们的最长公共子序列长度。这里的子序列不要求字符连续只要保持原顺序即可。举个例子text1 abcdetext2 ace。公共子序列可以是a、c、e、ae也可以是ace。其中ace最长长度为3所以答案就是3。注意abcde里a在第1位c在第3位e在第5位它们不需要挨在一起只需要保证在text1和text2中各自都是按顺序出现的。1.1 子序列和子串一字之差天壤之别面试里经常有人把子序列和子串搞混这是基础概念必须拿捏清楚。子串原字符串中连续的一段。子序列原字符串中按顺序挑出的字符不要求连续。生活化类比子串就像从一列火车里抽一节连续的车厢子序列则是从一列火车里按顺序挑几个人出来人不需要坐在相连的位置上。abcde的子串有ab、bc、de等它的子序列则有ae、bd、ace等。“bde”也是合法子序列因为它按b→d→e的顺序出现在原串中。这个区别直接决定了状态转移方程的写法。子串问题在字符不匹配时需要重新计数子序列问题因为有“跳过”的自由度转移方程要考虑“不选”的情况。LeetCode 1143之所以是动态规划入门的核心题正是因为它的状态设计思路能迁移到大量动规题型上。1.2 为什么贪心解决不了LCS拿到这类题第一反应往往是两个指针从前往后扫相同就匹配不同就跳。这不就完了吗我起初也这么想。尝试一个反例text1 abctext2 acb。从text1的a开始匹配text2的atext1的b尝试匹配text2的下一个字符c不匹配text2跳下一个b匹配成功text1的c继续找text2只有一个c但在b之前已经过去了匹配失败。贪心匹配得到的是ab长度2。但实际最长公共子序列是ac或ab长度也是2等一下虽然这个例子里贪心碰巧没输但你稍微改一下text1 abcdeftext2 abxdfe。贪心会尽量匹配前面的ab然后c在text2里找不到跳过d、e都匹配上了得到abde长度4。这没问题。再改text1 abcabtext2 aabb。贪心从左往右a匹配ab匹配a不匹配跳b匹配b得到ab然后text1的c跳过a找不到可匹配的字符b匹配最后的b得abb长度3实际的最优应该是aabb长度4。贪心的短视在“选择哪个相同的字符进行匹配”时暴露了它不知道未来还有多少字符等着。所以结论就是LCS这类问题具备最优子结构但局部贪心选择不能保证全局最优。你必须在每个位置保留“可能的最优长度”让后续决策在这些候选之上继续生长这就是动态规划切入的时机。1.3 状态定义为什么不叫dp[i]而叫dp[i][j]一维DP解决的是单序列问题比如最长递增子序列。而LCS是双序列问题两个字符串的匹配情况互相影响必然要用二维状态。定义dp[i][j]为text1的前i个字符和text2的前j个字符的最长公共子序列长度。这个定义里有几个点要反复确认“前i个字符”是包含0到的dp[0][j]表示text1为空串和text2的前j个字符的LCS显然等于0。dp[i][j]不一定以第i个字符或第j个字符结尾它记录的是一个前缀范围内的最佳结果。最终答案是dp[m][n]即两个完整字符串的最长公共子序列长度。很多新手的误区是把dp[i][j]定义成“以text1[i]和text2[j]结尾的LCS长度”。这个定义会导致转移方程极其别扭因为公共子序列不一定以两个字符串的某对相同字符结尾你还要额外维护一个全局最大值。而“前缀”式定义天然包含了全局信息是理解后续所有变体的根基。2. 状态转移方程从哪里来动态规划的核心不是记住方程而是能自己推导。题目做多了你会发现所有的二维DP都长得很像区别就在于“相等时怎么做不相等时怎么做”。2.1 从具体例子出发推演转移过程假设text1 abcdetext2 ace我们来看dp值是怎么填出来的。先初始化dp[i][0] 0dp[0][j] 0因为任何字符串和空串的公共子序列长度都是0。然后逐行填表i1text1[0]a。j1text2[0]a相等dp[1][1] dp[0][0] 1 1。j2text2[1]c不相等dp[1][2] max(dp[0][2], dp[1][1]) max(0, 1) 1。j3text2[2]e不相等dp[1][3] max(dp[0][3], dp[1][2]) max(0, 1) 1。i2text1[1]b。j1b vs a不相等dp[2][1] max(dp[1][1], dp[2][0]) max(1, 0) 1。j2b vs c不相等dp[2][2] max(dp[1][2], dp[2][1]) 1。j3b vs e不相等dp[2][3] max(dp[1][3], dp[2][2]) 1。i3text1[2]c。j1c vs a不相等dp[3][1] max(1, 0) 1。j2c vs c相等dp[3][2] dp[2][1] 1 2。j3c vs e不相等dp[3][3] max(dp[2][3], dp[3][2]) max(1, 2) 2。i4text1[3]d。j1不等dp[4][1] 1j2d vs c不等dp[4][2] max(dp[3][2], dp[4][1]) 2j3d vs e不等dp[4][3] max(dp[3][3], dp[4][2]) 2。i5text1[4]e。j1e vs a不等dp[5][1] 1j2e vs c不等dp[5][2] max(dp[4][2], dp[5][1]) 2j3e vs e相等dp[5][3] dp[4][2] 1 3。最终答案3和预期完全一致。把dp[i][j]的转移归纳成两条公式如果text1[i-1] text2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])注意代码里用的是i-1和j-1因为dp数组的第1位对应字符串的第0个字符这里存在一个索引偏移是初学者最容易写错的地方。2.2 为什么相等分支不需要比较另外两个方向很多人会有疑问两个字符相等时为什么不写成dp[i][j] max(dp[i-1][j-1] 1, dp[i-1][j], dp[i][j-1])万一不选这对相等的字符得到的结果更大呢答案是不会。这里有一条很重要的性质可以从逻辑上证明因为dp[i-1][j]表示text1前i-1个字符和text2前j个字符的LCS长度而dp[i-1][j-1]是text1前i-1个字符和text2前j-1个字符的LCS长度。多了一个字符text2[j-1]LCS长度要么不变要么增加1所以dp[i-1][j] dp[i-1][j-1]也就是说dp[i-1][j-1] 1 dp[i-1][j]不对这个不等式不成立因为dp[i-1][j-1] 1比dp[i-1][j]可能大也可能小。更严谨的证明思路是dp[i-1][j-1] dp[i-1][j] dp[i-1][j-1] 1。因为text2前j个字符比前j-1个字符最多多一个可匹配字符LCS长度最多增加1。同理dp[i-1][j-1] dp[i][j-1] dp[i-1][j-1] 1。所以当text1[i-1] text2[j-1]时我们可以在dp[i-1][j-1]的基础上把这对相同字符接上去得到dp[i-1][j-1] 1。这个值至少和dp[i-1][j]、dp[i][j-1]一样大或者说不会小于它们。因此直接用dp[i-1][j-1] 1即可不需要做三层max比较。这部分原理在面试时如果被追问能够讲清楚会非常有说服力。2.3 边界条件里藏着的小陷阱dp表的第0行和第0列全部初始化为0。这个初始化且只有这一步其余格子由转移方程自动填出。但有一个代码层面的坑值得单独说字符串的charAt索引和dp数组索引之间相差1。text1.charAt(i-1)对应的是dp[i]这一行的决策依据。如果直接用text1.charAt(i)去比较轻则漏掉最后一个字符重则数组越界。这种情况在面试白板编程时尤其容易发生我帮人review代码时见过太多次。3. 完整代码实现与空间优化理解了状态定义和转移方程写代码其实就剩最后一公里了。3.1 二维DP完整实现版以Python为例先用最直观的二维数组来实现def longestCommonSubsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) # dp[i][j] 表示 text1 前 i 个字符和 text2 前 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 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)使用了一个完整的二维数组。m和n分别是两个字符串的长度。LeetCode的测试数据最大在1000级别100万次操作完全能过。但如果两个字符串长度都是10000二维表就存不下了这时候要考虑空间优化。3.2 滚动数组优化把二维表压成一维数组观察转移方程dp[i][j]只依赖三个方向左上角dp[i-1][j-1]正上方dp[i-1][j]正左方dp[i][j-1]也就是说当前行只和上一行以及当前行左侧有关再往前的行的数据完全没必要保留。所以可以用一维数组滚动更新把空间从O(m×n)压缩到O(n)。实现时有一个关键点计算dp[j]时要用到左上角dp[i-1][j-1]但一维数组更新后上一行的dp[j-1]已经被当前行的值覆盖了。因此必须在覆盖之前先保存左上角的值。def longestCommonSubsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) # 空间优化只保留一行长度取 n1 dp [0] * (n 1) for i in range(1, m 1): prev 0 # 相当于 dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 先保存当前 dp[j]下一轮作为左上角使用 if text1[i - 1] text2[j - 1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j - 1]) prev temp return dp[n]这里的prev变量非常关键。一开始prev 0对应第i-1行的dp[0]也就是dp[i-1][0] 0。进入内层循环后当j1时如果字符相等dp[1] prev 1这里的prev就是dp[i-1][0]然后把temp也就是更新前的dp[1]即dp[i-1][1]保存为prev下一轮j2prev就是dp[i-1][1]正好是需要的左上角。这个技巧面试时写在白板上会加很多印象分。如果只写出二维DP也不会扣分但主动优化一版聊两句原理说明你真的理解这道题了。3.3 复杂度分析为什么空间可以进一步优化还有一种优化思路始终遍历较短的那个字符串作为内层循环让滚动数组的长度尽可能小。def longestCommonSubsequence(text1: str, text2: str) - int: # 如果 text2 更长交换确保内层数组较短 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): prev 0 for j in range(1, n 1): temp dp[j] if text1[i - 1] text2[j - 1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j - 1]) prev temp return dp[n]这不会改变时间复杂度但能进一步压空间常数。在极端场景下如果text2长度为1数组长度只有2空间开销几乎可以忽略。这种细节在实际工程里不常用但在算法竞赛或面试手撕环节是一个能体现功力的优化点。顺便补充一个工程化视角在真实业务里两个很长的文本做diffLCS只是中间步骤后续还要根据dp表回溯出具体的差异块。这时候空间优化就要谨慎因为回溯需要完整的二维dp表。面试如果只问长度滚动数组完美如果考官追问“那你能打印出最长公共子序列吗”就不能再用一维数组方案了得保留完整dp表。4. 常见问题与调试经验下面这些坑我见过身边的同事和一起刷题的朋友踩过很多次自己也栽过整理出来供参考。4.1 dp数组初始化易错点症状可能原因正确做法结果比预期大初始化时把dp[0][]或dp[][0]设置成了1任何字符串与空串的LCS长度都应为0结果少1比较字符时用了i和j而非i-1和j-1漏掉了首字符或尾字符统一用text1[i-1]与text2[j-1]比较相等时取了max(三个方向)试图用更保守的公式但没有理解相等时已经是最优相等时直接dp[i-1][j-1] 1记忆化递归超时递归函数没有缓存状态使用functools.lru_cache缓存二维状态或直接改迭代式DP这里重点说说第二行。假设text1 abctext2 a正确LCS长度为1。如果代码里图省事循环从i0, j0开始把dp[0][0]当初始状态比较的是text1[0]和text2[0]看似能算出1但一旦处理“text1第一个字符和text2最后一个字符匹配”的场景就会发生漏算或越界。老老实实从索引1开始遍历、让出第0行第0列作为边界是这套写法的定式。还有一点Python中初始化二维数组不要写成dp [[0] * (n 1)] * (m 1)这会创建m1个指向同一列表的引用。修改任意一行所有行一起变。我见过太多新手在这一行代码上debug半小时。正确写法是dp [[0] * (n 1) for _ in range(m 1)]或者用[[0] * (n 1)] * (m 1)的替代方案dp [[0 for _ in range(n 1)] for _ in range(m 1)]。4.2 谁动了我的最大值滚动数组debug实录有一次写滚动数组版本死活不对。字符相等时直接写dp[j] dp[j] 1结果有些用例偏大。原因就出在“加1”之前dp[j]已经被当前行左侧的更新影响了。正确的逻辑是相等时用上一行左上角的值加1而不是当前数组里的dp[j]自己加1。调试技巧是打印每一轮循环后的dp数组第1轮后: [0, 1, 1, 1] 第2轮后: [0, 1, 1, 1] 第3轮后: [0, 1, 2, 2] 第4轮后: [0, 1, 2, 2] 第5轮后: [0, 1, 2, 3]肉眼对比第3轮、第5轮的变化就能发现prev是不是保存对了。4.3 走出舒适区从“返回长度”升级到“输出具体子序列”如果面试官让打印出最长公共子序列本身该怎么办基于完整二维dp表从dp[m][n]开始倒推如果text1[i-1] text2[j-1]说明这个字符被匹配进来了加入结果序列向左上方移动i-1, 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]) res [] i, j m, n 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))如果题目要求所有公共子序列回溯时可以两边都走但结果数量可能指数级增长需要额外处理去重问题。这个属于竞赛级扩展面试极少考到。4.4 值得收藏的测试用例刷题时准备一组测试用例可以快速验证代码是否正确text1text2期望LCS长度说明0双空串abc0单空串abcabc3完全相等abcdef0完全不等abcdeace3经典示例abcacb2匹配顺序影响结果aaaaaa2重复字符边界abcdeffedcba1唯一匹配字符尤其最后一行两个字符串完全反向最长公共子序列长度为1很多人在这个用例上会把长度算成3因为“d、e、f在text1和text2里都有”。但没有一个字符在两个字符串中保持相同相对顺序的集合长度超过1。这种反向用例是检验状态转移理解的试金石。5. 变体题型与扩展思路同一个DP套路能延展出大量相关题目。面试中问LCS往往不是孤立的它会以各种变形出现。5.1 最长公共子串只要连续的部分把“子序列”改成“子串”约束变为字符必须连续。DP方程几乎是姊妹版dp[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][j] 0因为“连续”这个条件被打破了只能清零重新累积。最终答案是dp表中的最大值而不是dp[m][n]。对比LCS子序列允许断点所以不等时要取max延续之前的匹配子串不允许断点所以不等时直接清零。一个分支策略的不同就造成两种完全不同的题目。建议两个题一起刷效果翻倍。5.2 最长回文子序列LCS的间接应用题给定一个字符串s求它的最长回文子序列长度。很多人第一眼看不出来这和LCS有什么关系。解法把s反转得到rev(s)求s和rev(s)的最长公共子序列长度。为什么成立回文子序列从左往右读和从右往左读是一样的。那么它既是s的子序列也必然是rev(s)的子序列。反过来呢如果某个子序列同时出现在s和rev(s)中它是不是回文不一定但长度为LCS的公共子序列一定对应一个回文子序列详细证明可以看经典教材。这个转化思路在面试中非常常用它体现了“如何把未知问题归约到已知问题”的能力。5.3 最短公共超序列从LCS长度直接算出来给定两个字符串s1和s2找到一个最短的字符串使得s1和s2都是它的子序列。比如s1 abacs2 cab。最短公共超序列Shortest Common Supersequence, SCS长度可以直接用LCS算出来len(SCS) len(s1) len(s2) - len(LCS)重叠部分就是最长公共子序列。对s1abacs2cabLCS是ab或ac长度为2最短超序列长度为4 3 - 2 5。比如cabac长度5包含了abac和cab两个子序列。LCS的DP表还可以直接用来回溯SCS的具体内容属于“从一道题派生出一串题”的经典套路。5.4 LCS与编辑距离的关系编辑距离LeetCode 72是另一个著名的二维DP题它解决的是把s1变成s2需要的最少插入、删除、替换次数。编辑距离的DP思路和LCS有两个层面的相似都是双序列问题状态都定义为“前i个字符和前j个字符”。字符相等时直接继承对角线的结果不相等时LCS取max编辑距离取min加操作代价。区别在于目标不同LCS是找共同部分编辑距离是算转换成本。理解它们的相似与差异有助于建立DP的整体观。刷完1143再刷72会有一种“啊原来是同一套骨架”的顿悟感。我刷了这么多动态规划的题回头再看LeetCode 1143它最大的价值倒不是题本身而是它作为“双序列DP”的模板题把所有关键手法都集中在一个简单模型里前缀型状态定义、字符相等/不等的分支处理、滚动数组空间优化、二维表回溯解。这四个能力点几乎能覆盖大部分面试中的二维DP问题。建议不要背代码而是亲手画一次dp表用两个小字符串一步步填出来感受一下数字变化的规律。等你能不看任何参考资料从状态定义开始把整套推导完整写出来这道题才是真正过了。