day160—动态规划—最长公共子序列（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"），与递归版结果一致且执行效率更高。

函数源码（二）：