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

动态规划核心思路一句话讲透用二维数组dp[i][j]表示text1 的前 i 个字符 和 text2 的前 j 个字符 的最长公共子序列的长度。i表示的是第几个。所以下面的索引就是i-1我们只需要考虑两种情况如果 text1 的第 i 个字符 text2 的第 j 个字符 这个字符可以加入公共子序列所以dp[i][j] dp[i-1][j-1] 1前面 i-1 和 j-1 个字符的最长公共子序列加上这个新的公共字符如果两个字符不相等 最长公共子序列要么不包含 text1 的第 i 个字符要么不包含 text2 的第 j 个字符取两者的最大值 所以dp[i][j] max(dp[i-1][j], dp[i][j-1])完整解题步骤1. 初始化 dp 数组数组大小(m1) × (n1)其中 m 是 text1 的长度n 是 text2 的长度为什么要 1因为我们要表示前 0 个字符空字符串的情况边界条件dp[0][j] 0空字符串和任何字符串的公共子序列长度都是 0dp[i][0] 0任何字符串和空字符串的公共子序列长度都是 02. 遍历计算 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数组 vectorvectorint dp(m1,vectorint(n1,0)); //初始化 一共m1行 n1列.因为考虑前0行 所以要加1个 //遍历text1 for(int i 1;im;i){ //遍历text2 for(int j 1;jn;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]; } };