LeetCode 1143. 最长公共子序列 题目描述题目级别中等给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回0。一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如ace是abcde的子序列但aec不是abcde的子序列。示例 1:输入text1 abcde,text2 ace输出3解释最长公共子序列是ace它的长度为 3 。 解法一二维动态规划面对两个字符串的子序列匹配问题标准的起手式就是开辟一个二维 DP 数组。状态定义定义dp[i][j]表示text1的前i个字符和text2的前j个字符它们的最长公共子序列的长度。状态转移方程当我们考察text1[i]和text2[j]时只有两种情况两个字符相等 (text1[i] text2[j])说明我们找到了一个公共字符那么这个字符就可以接在它们前面的公共子序列之后。dp[i][j] dp[i - 1][j - 1] 1两个字符不相等 (text1[i] ! text2[j])说明这两个字符不可能同时出现在公共子序列的末尾。我们要么舍弃text1[i]看看text1[0...i-1]和text2[0...j]的匹配结果要么舍弃text2[j]看看text1[0...i]和text2[0...j-1]的匹配结果。我们取这两种选择中的最大值。dp[i][j] max(dp[i - 1][j], dp[i][j - 1])本解法高光点哨兵技巧代码中极其精妙地使用了text1 text1;在字符串头部人为加入了一个空格哨兵。这样不仅让字符串的有效下标从1开始更重要的是当我们在代码中调用i - 1和j - 1时绝对不会发生数组越界报错彻底免去了繁琐的边界初始化判断 C 代码实现 (二维 DP)classSolution{public:intlongestCommonSubsequence(string text1,string text2){intmtext1.size(),ntext2.size();// 极客技巧加空格哨兵让有效字符下标从 1 开始完美避开 i-1 越界问题text1 text1;text2 text2;// 开辟 DP 数组多开 10 个空间防止溢出intdp[m10][n10];memset(dp,0,sizeofdp);// 初始化为 0// 遍历所有状态for(inti1;im;i){for(intj1;jn;j){// 标准的状态转移if(text1[i]text2[j]){// 字符相等取左上角的值 1dp[i][j]dp[i-1][j-1]1;}else{// 字符不等取上方和左方的最大值dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}}returndp[m][n];}};进阶挑战你能否将空间复杂度优化到O ( min ⁡ ( M , N ) ) O(\min(M, N))O(min(M,N)) 解法二一维滚动数组降维打击在经典的二维状态转移方程中dp[i][j] dp[i - 1][j - 1] 1dp[i][j] max(dp[i - 1][j], dp[i][j - 1])仔细观察会发现我们在计算第i行的dp值时仅仅依赖于第i - 1行上一行和第i行当前行左边的值。至于再往前的历史数据我们根本不需要了。因此我们不需要维护整个巨大的二维矩阵只需要一个长度为N 1 N1N1的一维数组dp即可循环滚动唯一的难点在于dp[i - 1][j - 1]因为在更新一维数组时当前位置的左上角的值也就是还没被更新前的dp[j-1]会被提前覆盖掉。所以我们需要一个临时变量prev把它在被覆盖前给保护起来留给下一步使用。 C 代码实现 (空间优化版)classSolution{public:intlongestCommonSubsequence(string text1,string text2){// 让 text2 始终是较短的字符串这样一维数组就可以开得更小if(text1.size()text2.size()){swap(text1,text2);}intmtext1.size(),ntext2.size();// 只需要一个长度为 n 1 的一维数组vectorintdp(n1,0);for(inti1;im;i){// prev 用来记录“左上角”的值 (dp[i-1][j-1])intprevdp[0];for(intj1;jn;j){// temp 先把正上方的值 (也就是将要被覆盖的旧 dp[j]) 保存下来给下一轮的 prev 用inttempdp[j];if(text1[i-1]text2[j-1]){// 相等时使用保护好的左上角旧值 1dp[j]prev1;}else{// 不等时取上方 (旧 dp[j]) 和左方 (新 dp[j-1]) 的较大值dp[j]max(dp[j],dp[j-1]);}// 将当前旧的 dp[j] 赋值给 prev成为下一次循环的“左上角”prevtemp;}}returndp[n];}};