leetcode 1143最长公共子序列

一、完整代码精简注释class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m text1.length(), n text2.length(); // dp[i][j] 表示两个字符串前 i、前 j 个字符的最长公共子序列长度 vectorvectorint dp(m1, vectorint(n1, 0)); // 遍历两个字符串 for (int i 1; i m; i) { for (int j 1; j n; j) { // 字符相等左上角状态加 1 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]; } };二、动态规划五步总结1. 确定 dp 数组及下标含义vectorvectorint dp(m1, vectorint(n1, 0));dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。注意dp 中的 i、j 表示字符数量不是字符串下标。text1 前 i 个字符对应下标 0 到 i-1。text2 前 j 个字符对应下标 0 到 j-1。子序列可以不连续但必须保持原来的相对顺序。例如text1 abc text2 ac dp[2][1]比较 ab 和 a结果为 1 dp[3][2]比较 abc 和 ac结果为 22. 确定状态转移方程分为两种情况。情况一当前两个字符相等if (text1[i-1] text2[j-1]) { dp[i][j] dp[i-1][j-1] 1; }说明两个字符可以匹配最长公共子序列长度在左上角状态的基础上加 1。其中dp[i-1][j-1]两个字符串都不考虑当前最后一个字符时的最长公共子序列长度。1将当前匹配成功的字符加入公共子序列。例如text1 abc text2 ac 当前比较 c c dp[3][2] dp[2][1] 1 1 1 2情况二当前两个字符不相等else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); }因为两个末尾字符不相等所以它们不能同时作为公共子序列的最后一个字符。此时需要考虑两种情况dp[i-1][j]舍弃 text1 的最后一个字符保留 text2 的前 j 个字符。dp[i][j-1]舍弃 text2 的最后一个字符保留 text1 的前 i 个字符。因为要求最长公共子序列所以选择两种情况中的最大值。例如text1 abc text2 ab 当前比较 c ! b 情况一舍弃 c ab 和 ab dp[2][2] 2 情况二舍弃 b abc 和 a dp[3][1] 1 因此 dp[3][2] max(2, 1) 2核心理解字符相等就匹配字符不相等就分别尝试舍弃一个字符选择更优的结果。3. 初始化 dp 数组vectorvectorint dp(m1, vectorint(n1, 0));二维数组大小为 (m1) × (n1)所有元素初始化为 0。为什么需要加 1因为需要额外的一行和一列表示空字符串。dp[0][j] 0text1 为空字符串 dp[i][0] 0text2 为空字符串只要其中一个字符串为空最长公共子序列长度就为 0。这样可以直接从 dp[1][1] 开始计算不需要单独处理边界。特别注意dp[i][j] // 前 i 个字符和前 j 个字符 text1[i-1] // text1 前 i 个字符中的最后一个 text2[j-1] // text2 前 j 个字符中的最后一个4. 确定遍历顺序for (int i 1; i m; i) { for (int j 1; j n; j) { // 状态转移 } }遍历顺序从上到下、从左到右。因为计算 dp[i][j] 时依赖三个位置dp[i-1][j-1]左上方 dp[i-1][j]上方 dp[i][j-1]左方所以必须保证这三个位置已经计算完成才能计算当前位置。外层循环负责遍历 text1内层循环负责遍历 text2不断更新二维 dp 数组。5. 举例推导 dp 数组假设text1 abc; text2 ab;最终 dp 数组为空 a b 空 0 0 0 a 0 1 1 b 0 1 2 c 0 1 2计算过程dp[1][1] a a dp[1][1] dp[0][0] 1 1 dp[1][2] a ! b dp[1][2] max(dp[0][2], dp[1][1]) 1 dp[2][1] b ! a dp[2][1] max(dp[1][1], dp[2][0]) 1 dp[2][2] b b dp[2][2] dp[1][1] 1 2 dp[3][1] c ! a dp[3][1] max(dp[2][1], dp[3][0]) 1 dp[3][2] c ! b dp[3][2] max(dp[2][2], dp[3][1]) 2最终return dp[m][n]; // 返回 dp[3][2] 2最长公共子序列为 ab长度为 2。三、复杂度分析时间复杂度O(m * n)使用两层循环遍历两个字符串每个 dp 状态只计算一次。空间复杂度O(m * n)创建了一个 (m1) × (n1) 的二维 dp 数组用于保存所有子问题的结果。四、核心总结本题使用二维动态规划求两个字符串的最长公共子序列长度。子序列不要求连续但是必须保持字符的相对顺序。dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度。dp 数组大小为 (m1) × (n1)多出来的第一行和第一列表示空字符串全部初始化为 0。dp 中的 i、j 表示字符数量而字符串下标从 0 开始因此比较字符时使用 text1[i-1] 和 text2[j-1]。当两个字符相等时说明当前字符可以匹配状态转移为 dp[i][j] dp[i-1][j-1] 1。当两个字符不相等时分别考虑舍弃 text1 的最后一个字符和舍弃 text2 的最后一个字符选择公共子序列长度较大的结果即 dp[i][j] max(dp[i-1][j], dp[i][j-1])。遍历顺序为从上到下、从左到右因为当前状态依赖左上方、上方和左方已经计算完成的状态。整个 dp 是一个二维数组每个位置保存对应两个字符串前缀的最长公共子序列长度最终返回右下角的 dp[m][n]。时间复杂度为 O(mn)空间复杂度为 O(mn)。最重要的代码模板// 当前字符相等 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]); }一句话记忆字符相等左上角加 1字符不相等上方和左方取最大值。这道题最重要的就是理解dp[i][j]的含义以及为什么字符不相等时需要分别舍弃一个字符。