力扣HOT（100）54多维动态规划-最长公共子序列

动态规划核心思路（一句话讲透）

用二维数组dp[i][j]表示：text1 的前 i 个字符 和 text2 的前 j 个字符 的最长公共子序列的长度。i表示的是第几个。所以下面的索引就是i-1

我们只需要考虑两种情况：

1. 如果 text1 的第 i 个字符 == text2 的第 j 个字符： 这个字符可以加入公共子序列，所以dp[i][j] = dp[i-1][j-1] + 1（前面 i-1 和 j-1 个字符的最长公共子序列，加上这个新的公共字符）
2. 如果两个字符不相等： 最长公共子序列要么不包含 text1 的第 i 个字符，要么不包含 text2 的第 j 个字符，取两者的最大值 所以dp[i][j] = max(dp[i-1][j], dp[i][j-1])

完整解题步骤

1. 初始化 dp 数组

• 数组大小：(m+1) × (n+1)，其中 m 是 text1 的长度，n 是 text2 的长度
• 为什么要 + 1？因为我们要表示前 0 个字符（空字符串）的情况
• 边界条件：
  • dp[0][j] = 0：空字符串和任何字符串的公共子序列长度都是 0
  • dp[i][0] = 0：任何字符串和空字符串的公共子序列长度都是 0

2. 遍历计算 dp 数组

• 外层循环：i 从 1 到 m（遍历 text1 的每个字符）
• 内层循环：j 从 1 到 n（遍历 text2 的每个字符）
  • 如果text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
  • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. 返回结果

dp[m][n]就是两个完整字符串的最长公共子序列的长度。

class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(); int n = text2.size(); //初始化dp数组： vector<vector<int>> dp(m+1,vector<int>(n+1,0)); //初始化 一共m+1行 n+1列.因为考虑前0行 所以要加1个 //遍历text1 for(int i = 1;i<=m;i++){ //遍历text2 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]; } };