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 <= 1000text1和text2仅由小写英文字符组成。
解决方案（一）：
这段代码的核心功能是求解两个字符串的最长公共子序列（LCS）长度，采用「类内辅助函数 + 记忆化递归」的思路实现，通过缓存子问题结果避免重复计算，将暴力递归的指数级复杂度优化为多项式级别，是 LCS 问题的经典高效解法。
核心逻辑
成员变量作用：
s_/t_：类内备份的两个输入字符串，供辅助递归函数dfs直接访问，无需频繁传参；memo：二维记忆化数组（n×m，n/m分别为s/t的长度），memo[i][j] = -1表示子问题dfs(i,j)未计算，计算后缓存结果，替代 Python 的@cache装饰器。
辅助递归函数
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]，统一返回。
- 参数含义：
主函数
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 的动态规划状态转移本质；
- 封装性好：辅助函数设为类内私有，通过成员变量共享状态，对外仅暴露简洁的接口。
总结
- 核心思路：用记忆化递归缓存子问题结果，通过 “字符相等 / 不等” 的状态转移求解 LCS 长度；
- 关键操作：
memo数组的缓存是效率核心，避免重复计算相同子问题； - 功能效果：能高效求解任意两个字符串的 LCS 长度，无重复计算、无遗漏，符合工程化编程规范。
以输入s="abcde"、t="ace"为例，最终返回3（LCS 为 "ace"），完全符合预期。
函数源码（一）：
class Solution { public: // 类内成员变量：存储输入字符串+记忆化数组（替代@cache） string s_; string t_; vector<vector<int>> memo; // memo[i][j] 缓存 dfs(i,j) 的结果 // 辅助递归函数：dfs(i,j) 表示 s[0..i] 和 t[0..j] 的最长公共子序列长度 int dfs(int i, int j) { // 递归边界：任一字符串遍历完，LCS长度为0 if (i < 0 || j < 0) { return 0; } // 记忆化优化：已计算过该子问题，直接返回缓存值 if (memo[i][j] != -1) { return memo[i][j]; } int res = 0; // 状态转移1：当前字符相等，LCS长度+1 if (s_[i] == t_[j]) { res = dfs(i - 1, j - 1) + 1; } // 状态转移2：当前字符不等，取“删s[i]”或“删t[j]”的最大值 else { res = max(dfs(i - 1, j), dfs(i, j - 1)); } // 缓存结果，避免重复计算 return memo[i][j] = res; } int longestCommonSubsequence(string s, string t) { int n = s.size(), m = t.size(); // 初始化类内成员变量 s_ = s; t_ = t; // 初始化记忆化数组：n行m列，初始值-1（表示未计算） memo.assign(n, vector<int>(m, -1)); // 从两个字符串的最后一个字符开始递归 return dfs(n - 1, m - 1); } };
解决方案（二）：
这段代码的核心功能是用迭代版动态规划（DP）求解两个字符串的最长公共子序列（LCS）长度，相比递归记忆化版本更高效（无递归调用开销），是 LCS 问题的最优迭代解法。
核心逻辑
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），无需额外处理边界。
- 之所以用
初始化：构建
(m+1)×(n+1)的二维数组dp，所有元素初始化为 0。这是因为 “空串和任何字符串的 LCS 长度都是 0”，对应dp[0][*] = 0、dp[*][0] = 0，天然满足递归边界条件。状态转移（核心迭代逻辑）：双层循环遍历两个字符串的所有字符组合（
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])。
- 若
结果输出：
dp[m][n]存储了text1完整字符串和text2完整字符串的 LCS 长度，直接返回该值即可。
关键特点
- 无递归开销：迭代方式避免了递归的函数调用栈开销，空间 / 时间效率更优；
- 边界简化：通过
dp数组多开一行一列（索引 0），天然处理空串边界，无需额外判断； - 时间复杂度O(m×n)、空间复杂度O(m×n)，是 LCS 问题的标准迭代解法。
总结
- 核心思路：用二维 DP 数组自底向上迭代计算所有子问题，避免递归重复计算；
- 关键设计：DP 数组索引偏移（
i-1/j-1）简化边界处理，状态转移逻辑与递归版完全一致； - 功能效果：高效求解 LCS 长度，是工程中更常用的迭代实现方式。
以text1="abcde"、text2="ace"为例，最终dp[5][3] = 3（LCS 为 "ace"），与递归版结果一致且执行效率更高。
函数源码（二）：
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(); int n = text2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { 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]; } };