leetcode 1143. Longest Common Subsequence

目录

题目描述

第一步，明确并理解dp数组及下标的含义

第二步，分析明确并理解递推公式

第三步，理解dp数组如何初始化

第四步，理解遍历顺序

代码

---

题目描述

这道题和第718题的区别就是，本题求的是最长公共子序列的长度，第718题求的是最长公共子数组的长度。子序列可以不是连续的，子数组则必须是连续的。两道题的分析方法是一样的。

第一步，明确并理解dp数组及下标的含义

用下标(i-1)遍历text1数组，用下标(j-1)遍历text2数组。

        int len1 = text1.size();

        int len2 = text2.size();

        //i的取值范围是[1,len1]

        //j的取值范围是[1,len2]

        //dp[i][j]表示字符串text1[0,i-1]和字符串text2[0,j-1]的最长公共【子序列】的长度

按照这样的定义，dp[len1][len2]就是答案。本题dp数组的含义与第718题不一样。

第二步，分析明确并理解递推公式

 //当i!=0 && j!=0时,分两种情况：

 //如果text1[i-1]==text2[j-1],dp[i][j]=dp[i-1][j-1]+1

 //如果text1[i-1]!=text2[j-1],dp[i][j]应该为dp[i-1][j]和dp[i][j-1]中较大的一个

第三步，理解dp数组如何初始化

        //dp[0][j]表示text1为空,显然此时text1和text2没有公共【子序列】,dp[0][j]都应该初始化为0

        //dp[i][0]表示text2为空,显然此时text1和text2没有公共【子序列】,dp[i][0]都应该初始化为0

        //当i!=0 && j!=0时,分两种情况：

        //如果text1[i-1]==text2[j-1],dp[i][j]=dp[i-1][j-1]+1,即后面的dp[i][j]由前面的dp[i-1][j-1]覆盖计算,因此dp[i][j]可以不初始化，或者为了写代码方便可以统一初始化为0。

        //如果text1[i-1]!=text2[j-1],dp[i][j]应该为dp[i-1][j]和dp[i][j-1]中较大的一个,后面的dp[i][j]由前面的dp[i-1][j]或者前面的dp[i][j-1]覆盖计算，因此dp[i][j]可以不初始化，或者为了写代码方便可以统一初始化为0。

第四步，理解遍历顺序

由递推公式，可知i和j都应该从小到大遍历。注意i的取值范围是[1,len1]，j的取值范围是[1,len2]。

代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int len1 = text1.size();int len2 = text2.size();//i的取值范围是[1,len1]//j的取值范围是[1,len2]//dp[i][j]表示字符串text1[0,i-1]和字符串text2[0,j-1]的最长公共【子序列】的长度//dp[0][j]表示text1为空,显然此时text1和text2没有公共【子序列】,dp[0][j]都应该初始化为0//dp[i][0]表示text2为空,显然此时text1和text2没有公共【子序列】,dp[i][0]都应该初始化为0//当i!=0 && j!=0时,分两种情况：//如果text1[i-1]==text2[j-1],dp[i][j]=dp[i-1][j-1]+1,即后面的dp[i][j]由前面的dp[i-1][j-1]覆盖计算,因此dp[i][j]可以不初始化，或者为了写代码方便可以统一初始化为0。//如果text1[i-1]!=text2[j-1],dp[i][j]应该为dp[i-1][j]和dp[i][j-1]中较大的一个,后面的dp[i][j]由前面的dp[i-1][j]或者前面的dp[i][j-1]覆盖计算，因此dp[i][j]可以不初始化，或者为了写代码方便可以统一初始化为0。vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));for(int i = 1;i <= len1;i++){for(int j =1;j <= len2;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[len1][len2];}
};