LeetCode 1143 最长公共子序列（LCS）题解：从递归到 O(m·n) 动态规划的完整演进-港品优选

LeetCode 1143 最长公共子序列（LCS）题解：从递归到 O(m·n) 动态规划的完整演进

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文以 hints/longest-common-subsequence.md 的提示脉络为主线，系统讲解 LeetCode 1143「最长公共子序列（Longest Common Subsequence，LCS）」的五种解法：纯递归、自顶向下记忆化、自底向上表格化、双数组空间优化与单数组最优解。文中所有复杂度结论与递推公式均可在本仓库 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^(m+n))）必须被优化。

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(i+1, j+1)；
否则返回max(dfs(i+1, j), dfs(i, j+1))；
从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^{m+n})$ —— 每个不匹配节点都分裂出两个分支；
空间复杂度：$O(m+n)$ —— 递归调用栈深度。

其中 $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[i+1][j+1]、dp[i+1][j]、dp[i][j+1]均已就绪。

算法步骤

创建(m+1) x (n+1)的全 0 二维数组dp；
i从m-1递减到0，j从n-1递减到0；
若text1[i] == text2[j]，dp[i][j] = 1 + dp[i+1][j+1]；
否则dp[i][j] = max(dp[i+1][j], dp[i][j+1])；
返回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 表的可视化（结果为 3，"ace" 即 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两个长度为n+1的数组；
i从m-1递减到0，内层j从n-1递减到0：用prev[j+1]、prev[j]、curr[j+1]计算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[i+1][j]）在覆盖前先用临时变量prev保存，供下一次迭代的"对角线"引用使用。

算法步骤

若text1更短则交换，保证空间最小；
初始化长度为n+1的单个数组dp；
i从m-1递减到0：
- 令prev = 0（代表dp[i+1][n]）；
- j从n-1递减到0：
  - 保存temp = dp[j]（覆盖前的旧值）；
  - 字符匹配：dp[j] = 1 + prev；
  - 否则：dp[j] = max(dp[j], dp[j+1])；
  - 更新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^{m+n})$	$O(m+n)$（调用栈）	决策树穷举
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 表的维度应为(m+1) x (n+1)，多出的一行一列对应"空串"这一边界状态。字符匹配时访问dp[i+1][j+1]，若表尺寸不够或循环边界写错，就会产生数组越界。可参考 c/1143-longest-common-subsequence.c 中显式初始化首行首列的写法，从根上规避越界。

陷阱三：自底向上的迭代方向错误

逆序（从串尾向串头）填充时，必须保证计算dp[i][j]前，dp[i+1][j+1]、dp[i+1][j]、dp[i][j+1]三个依赖值已经算好。方向写反会让算法读到未计算的脏值。若采用正向遍历（如 C 实现），则需保证dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]先行就绪——两条路线的依赖顺序恰好镜像。

仓库中的完整实现全景

本题在仓库中覆盖了 10 种语言，全部为可直接运行的标准解法，便于横向对比各语言的 DP 写法差异：

Python：python/1143-longest-common-subsequence.py
C++：cpp/1143-longest-common-subsequence.cpp
Java：java/1143-longest-common-subsequence.java（含记忆化 + 迭代双版本）
JavaScript：javascript/1143-longest-common-subsequence.js（含 Top-Down / Bottom-Up / 空间优化共四种版本）
C：c/1143-longest-common-subsequence.c（正向遍历版本）
Go：go/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），仅供参考

企业官网建设流程全解析