动态规划：最长公共子序列（LeetCode-1143）

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

**输入：**text1 = "abcde", text2 = "ace" **输出：**3 **解释：**最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

**输入：**text1 = "abc", text2 = "abc" **输出：**3 **解释：**最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

**输入：**text1 = "abc", text2 = "def" **输出：**0 **解释：**两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

解决方案一：记忆化递归

这段代码的核心功能是求解两个字符串的最长公共子序列（LCS）长度，采用「类内辅助函数 + 记忆化递归」的思路实现，通过缓存子问题结果避免重复计算，将暴力递归的指数级复杂度优化为多项式级别，是 LCS 问题的经典高效解法。

核心逻辑

1. 成员变量作用：
   • s_/t_：类内备份的两个输入字符串，供辅助递归函数 dfs 直接访问，无需频繁传参；
   • memo：二维记忆化数组（n×m，n/m分别为 s/t 的长度），memo[i][j] = -1 表示子问题 dfs(i,j) 未计算，计算后缓存结果，替代 Python 的 @cache 装饰器。
2. 辅助递归函数 dfs(i,j) 逻辑：
   • 参数含义：i/j分别表示考虑 s[0..i] 和 t[0..j] 的子串范围；
   • 递归边界：i<0 或 j<0（任一子串遍历完毕），LCS 长度为 0；
   • 记忆化优化：若 memo[i][j]≠-1，直接返回缓存值，避免重复递归；
   • 核心状态转移：
     • 字符相等：s_[i]==t_[j] 时，该字符属于 LCS，长度 =dfs(i-1,j-1)+1（前 i-1/j-1 的 LCS 长度 + 1）；
     • 字符不等：取 max(dfs(i-1,j), dfs(i,j-1))（删 s[i] 或删 t[j] 后的 LCS 最大值）；
   • 结果缓存：将计算结果存入 memo[i][j]，统一返回。
3. 主函数 longestCommonSubsequence 逻辑：
   • 初始化：备份输入字符串到 s_/t_，初始化 memo 为 n×m 的二维数组（初始值 - 1）；
   • 启动递归：从两个字符串的最后一个字符（i=n-1,j=m-1）开始计算，返回最终 LCS 长度。

关键特点

• 效率优化：记忆化数组 memo 将时间复杂度从 O(2n+m) 降至 O(n×m)，空间复杂度为 O(n×m)（存储记忆化数组）；
• 逻辑清晰：递归函数聚焦'当前字符是否相等'的二选一决策，符合 LCS 的动态规划状态转移本质；
• 封装性好：辅助函数设为类内私有，通过成员变量共享状态，对外仅暴露简洁的接口。

总结

1. 核心思路：用记忆化递归缓存子问题结果，通过'字符相等 / 不等'的状态转移求解 LCS 长度；
2. 关键操作：memo 数组的缓存是效率核心，避免重复计算相同子问题；
3. 功能效果：能高效求解任意两个字符串的 LCS 长度，无重复计算、无遗漏，符合工程化编程规范。

以输入 s="abcde"、t="ace" 为例，最终返回 3（LCS 为 "ace"），完全符合预期。

解决方案二：迭代动态规划

这段代码的核心功能是用迭代版动态规划（DP）求解两个字符串的最长公共子序列（LCS）长度，相比递归记忆化版本更高效（无递归调用开销），是 LCS 问题的最优迭代解法。

核心逻辑

1. DP 数组定义：dp[i][j] 表示 text1[0..i-1]（前 i 个字符）和 text2[0..j-1]（前 j 个字符）的最长公共子序列长度。
   • 之所以用 i-1/j-1 而非 i/j，是为了让 dp[0][j] 和 dp[i][0] 自然表示'空串与任意子串'的 LCS 长度（值为 0），无需额外处理边界。
2. 初始化：构建 (m+1)×(n+1) 的二维数组 dp，所有元素初始化为 0。这是因为'空串和任何字符串的 LCS 长度都是 0'，对应 dp[0][*] = 0、dp[*][0] = 0，天然满足递归边界条件。
3. 状态转移（核心迭代逻辑）：双层循环遍历两个字符串的所有字符组合（i 从 1 到 m，j 从 1 到 n）：
   • 若 text1[i-1] == text2[j-1]：当前字符属于 LCS，dp[i][j] = dp[i-1][j-1] + 1（前 i-1/j-1 个字符的 LCS 长度 + 1）；
   • 若字符不相等：取'删 text1 第 i 个字符'或'删 text2 第 j 个字符'的最大值，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
4. 结果输出：dp[m][n] 存储了 text1 完整字符串和 text2 完整字符串的 LCS 长度，直接返回该值即可。

关键特点

• 无递归开销：迭代方式避免了递归的函数调用栈开销，空间 / 时间效率更优；
• 边界简化：通过 dp 数组多开一行一列（索引 0），天然处理空串边界，无需额外判断；
• 时间复杂度 O(m×n)、空间复杂度 O(m×n)，是 LCS 问题的标准迭代解法。

总结

1. 核心思路：用二维 DP 数组自底向上迭代计算所有子问题，避免递归重复计算；
2. 关键设计：DP 数组索引偏移（i-1/j-1）简化边界处理，状态转移逻辑与递归版完全一致；
3. 功能效果：高效求解 LCS 长度，是工程中更常用的迭代实现方式。

以 text1="abcde"、text2="ace" 为例，最终 dp[5][3] = 3（LCS 为 "ace"），与递归版结果一致且执行效率更高。