LeetCode 1143 最长公共子序列LCS题解从递归到 O(m·n) 动态规划的完整演进【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文以 hints/longest-common-subsequence.md 的提示脉络为主线系统讲解 LeetCode 1143「最长公共子序列Longest Common SubsequenceLCS」的五种解法纯递归、自顶向下记忆化、自底向上表格化、双数组空间优化与单数组最优解。文中所有复杂度结论与递推公式均可在本仓库 python/1143-longest-common-subsequence.py、cpp/1143-longest-common-subsequence.cpp 等源码中得到印证。读完本文你将掌握 LCS 的核心递推思想、四种空间优化技巧的推导过程以及如何规避子串/子序列混淆、DP 表越界与迭代方向错误三大高频陷阱。问题定义与前置知识题目要求给定两个字符串text1和text2返回它们的最长公共子序列的长度。子序列subsequence是指在不改变剩余字符相对顺序的前提下删除部分或全部字符后得到的新序列子序列不要求字符在原串中连续。在动手解题前建议先具备以下四项基础能力对应 articles/longest-common-subsequence.md 的 Prerequisites 章节递归Recursion能把大问题拆解为子问题理解递归调用栈的展开与回溯动态规划·记忆化Memoization通过缓存重叠子问题的结果避免重复计算动态规划·表格化Tabulation利用二维数组自底向上地构建答案空间优化Space Optimization识别递推中真正依赖的前一状态把二维 DP 压缩为一维。提示速览目标复杂度与三步思考路径hints/longest-common-subsequence.md 给出了求解本题的思考指引可以浓缩为以下三点复杂度目标最优解应达到或优于O(m * n)时间、O(m * n)空间m为text1长度n为text2长度。这意味着纯指数递归O(2^(mn))必须被优化。Hint 1 —— 用递归决策树思考同时递归遍历两个字符串每一步都可以看作决策树上的一个节点。Hint 2 —— 明确每一步的两个分支若text1[i] text2[j]两个指针同时前移公共子序列长度 1否则分别尝试只跳过text1[i]与只跳过text2[j]两条路径递归求解后取两者最大值。该朴素递归是指数级的需要优化。Hint 3 —— 用记忆化消除冗余当任一索引越界时返回0用哈希表或二维数组缓存(i, j)的递归结果避免重复计算。下面按从朴素到最优的顺序逐层展开这五种解法。方法一纯递归 —— 用决策树理解问题结构直觉两个字符串逐字符比较字符匹配就计入 LCS 并同时后移双指针不匹配则分别跳过其中一个串的当前字符取两种选择中的最优。这天然构成一棵指数级扩展的决策树。算法步骤定义递归函数dfs(i, j)i、j分别为text1、text2的当前索引边界条件任一索引到达串尾返回0若text1[i] text2[j]计入该字符并递归dfs(i1, j1)否则返回max(dfs(i1, j), dfs(i, j1))从dfs(0, 0)开始。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: def dfs(i, j): if i len(text1) or j len(text2): return 0 if text1[i] text2[j]: return 1 dfs(i 1, j 1) return max(dfs(i 1, j), dfs(i, j 1)) return dfs(0, 0)复杂度时间复杂度$O(2^{mn})$ —— 每个不匹配节点都分裂出两个分支空间复杂度$O(mn)$ —— 递归调用栈深度。其中 $m$ 为text1长度$n$ 为text2长度。方法二自顶向下动态规划记忆化直觉指数递归的瓶颈在于大量重叠子问题例如dfs(2, 3)可能被多个不同分支反复调用。把每个(i, j)的结果缓存进 memo 表后每个状态至多计算一次指数级立刻降为多项式级。这也是提示文档 Hint 3 的核心建议。算法步骤建立以(i, j)为键的记忆化表计算dfs(i, j)前先查表命中直接返回未命中则沿用递归逻辑计算结果并写回缓存其余逻辑与纯递归完全一致。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: memo {} def dfs(i, j): if i len(text1) or j len(text2): return 0 if (i, j) in memo: return memo[(i, j)] if text1[i] text2[j]: memo[(i, j)] 1 dfs(i 1, j 1) else: memo[(i, j)] max(dfs(i 1, j), dfs(i, j 1)) return memo[(i, j)] return dfs(0, 0)Java 的经典写法是维护memo[i][j]二维数组并以-1标记未计算状态仓库中的 java/1143-longest-common-subsequence.java 同时给出了 memoized 版与迭代版两种实现可直接对照阅读。JavaScript 版本见 javascript/1143-longest-common-subsequence.js其中用null初始化 memo 表表示未见过。复杂度时间复杂度$O(m * n)$ —— 每个状态只计算一次空间复杂度$O(m * n)$ —— memo 表大小。方法三自底向上动态规划表格化直觉与其从dfs(0, 0)向下递归不如从字符串末尾向前迭代填充二维表。定义dp[i][j]为子串text1[i:]与text2[j:]的 LCS 长度。按逆序处理索引可以保证计算dp[i][j]时它依赖的三个值dp[i1][j1]、dp[i1][j]、dp[i][j1]均已就绪。算法步骤创建(m1) x (n1)的全 0 二维数组dpi从m-1递减到0j从n-1递减到0若text1[i] text2[j]dp[i][j] 1 dp[i1][j1]否则dp[i][j] max(dp[i1][j], dp[i][j1])返回dp[0][0]。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: dp [[0 for j in range(len(text2) 1)] for i in range(len(text1) 1)] for i in range(len(text1) - 1, -1, -1): for j in range(len(text2) - 1, -1, -1): if text1[i] text2[j]: dp[i][j] 1 dp[i 1][j 1] else: dp[i][j] max(dp[i][j 1], dp[i 1][j]) return dp[0][0]源码印证仓库中的多语言实现几乎全部采用这一经典写法可以直接对照python/1143-longest-common-subsequence.py —— 与上文完全一致的逆序遍历表格化实现cpp/1143-longest-common-subsequence.cpp —— 注释中给出了text1 abcde、text2 ace时 DP 表的可视化结果为 3ace 即 LCS便于理解每个单元格的填充过程go/1143-longest-common-subsequence.go —— 相同递推的 Go 版本c/1143-longest-common-subsequence.c —— 采用正向遍历的等价写法dp[i][j]表示text1[0...i-1]与text2[0...j-1]的 LCS递推为dp[i][j] dp[i-1][j-1] 1匹配时或max(dp[i-1][j], dp[i][j-1])不匹配时并显式初始化首行首列为 0。这一对照说明只要保证依赖状态先行计算遍历方向正逆皆可。复杂度时间复杂度$O(m * n)$空间复杂度$O(m * n)$。方法四空间优化 —— 双一维数组滚动直觉观察递推式可知dp[i][j]只依赖当前行与下一行。因此无需保留整张二维表两个一维数组即可完成滚动prev保存下一行curr保存当前行每处理完一行后交换。算法步骤若text1更短则交换两串让空间与较短的串成正比初始化prev、curr两个长度为n1的数组i从m-1递减到0内层j从n-1递减到0用prev[j1]、prev[j]、curr[j1]计算curr[j]随后交换prev与curr返回prev[0]。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: if len(text1) len(text2): text1, text2 text2, text1 prev [0] * (len(text2) 1) curr [0] * (len(text2) 1) for i in range(len(text1) - 1, -1, -1): for j in range(len(text2) - 1, -1, -1): if text1[i] text2[j]: curr[j] 1 prev[j 1] else: curr[j] max(curr[j 1], prev[j]) prev, curr curr, prev return prev[0]复杂度时间复杂度$O(m * n)$空间复杂度$O(min(m, n))$ —— 交换两串后数组长度始终等于较短串长度 1。方法五最优解 —— 单数组 临时变量直觉还可以进一步压缩只用一个数组dp加一个临时变量。在行内从右向左迭代时位置j的旧值二维视角下的dp[i1][j]在覆盖前先用临时变量prev保存供下一次迭代的对角线引用使用。算法步骤若text1更短则交换保证空间最小初始化长度为n1的单个数组dpi从m-1递减到0令prev 0代表dp[i1][n]j从n-1递减到0保存temp dp[j]覆盖前的旧值字符匹配dp[j] 1 prev否则dp[j] max(dp[j], dp[j1])更新prev temp返回dp[0]。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: if len(text1) len(text2): text1, text2 text2, text1 dp [0] * (len(text2) 1) for i in range(len(text1) - 1, -1, -1): prev 0 for j in range(len(text2) - 1, -1, -1): temp dp[j] if text1[i] text2[j]: dp[j] 1 prev else: dp[j] max(dp[j], dp[j 1]) prev temp return dp[0]复杂度时间复杂度$O(m * n)$空间复杂度$O(min(m, n))$。五种解法复杂度对比总表方法时间空间核心手段1. 纯递归$O(2^{mn})$$O(mn)$调用栈决策树穷举2. 自顶向下记忆化$O(m*n)$$O(m*n)$缓存(i,j)结果3. 自底向上表格化$O(m*n)$$O(m*n)$二维表逆序填充4. 双数组滚动$O(m*n)$$O(min(m,n))$两行滚动交换5. 单数组最优$O(m*n)$$O(min(m,n))$临时变量保存对角线从表中可以清晰看到时间复杂度的跃迁发生在方法一 → 方法二/三指数级 → 多项式级空间复杂度的进一步收敛发生在方法三 → 方法四/五。实战中方法三最直观、最不易出错内存受限或追求极致时选用方法五。常见陷阱与规避陷阱一把子序列当成子串子序列不要求连续子串要求连续。最典型的错误是字符不匹配时把计数清零——那求到的是最长公共子串而非 LCS。LCS 在字符不匹配时必须取跳过其中一个字符两种路径的最大值绝不能清零重来。陷阱二DP 表索引的 Off-by-One 错误二维 DP 表的维度应为(m1) x (n1)多出的一行一列对应空串这一边界状态。字符匹配时访问dp[i1][j1]若表尺寸不够或循环边界写错就会产生数组越界。可参考 c/1143-longest-common-subsequence.c 中显式初始化首行首列的写法从根上规避越界。陷阱三自底向上的迭代方向错误逆序从串尾向串头填充时必须保证计算dp[i][j]前dp[i1][j1]、dp[i1][j]、dp[i][j1]三个依赖值已经算好。方向写反会让算法读到未计算的脏值。若采用正向遍历如 C 实现则需保证dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]先行就绪——两条路线的依赖顺序恰好镜像。仓库中的完整实现全景本题在仓库中覆盖了 10 种语言全部为可直接运行的标准解法便于横向对比各语言的 DP 写法差异Pythonpython/1143-longest-common-subsequence.pyCcpp/1143-longest-common-subsequence.cppJavajava/1143-longest-common-subsequence.java含记忆化 迭代双版本JavaScriptjavascript/1143-longest-common-subsequence.js含 Top-Down / Bottom-Up / 空间优化共四种版本Cc/1143-longest-common-subsequence.c正向遍历版本Gogo/1143-longest-common-subsequence.go其余见typescript/、kotlin/、swift/、rust/、csharp/、dart/目录下的1143-longest-common-subsequence.*文件。延伸LCS 思想的迁移应用掌握 LCS 的递推结构后可自然迁移到同一 DP 思想家族的题目例如 longest-palindromic-subsequence.md把原串与其反转串求 LCS 即可得到最长回文子序列长度以及articles/目录下的 edit-distance.md、interleaving-string.md 等二维字符串 DP 问题。理解匹配取对角线 1、不匹配取相邻较大值这一核心递推是解决整类双序列 DP 问题的关键。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考