1143. 最长公共子序列

总体思路还是718. 最长重复子数组，一图胜千言，但是本题是子序列，也就是说可以不连续，本题不采用以text1[i] text2[j] 结尾，因为是求子序列不合适。

Code

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), 0));
        for(int i=0;i<text1.size();i++) {
            for(int j=0;j<text2.size();j++) {
                if(i>0&&j>0&&text1[i]==text2[j]) dp[i][j]=dp[i-1][j-1]+1;
                else if(text1[i]==text2[j]) dp[i][j]=1;
                else if(i>0&&j>0) dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                else if(i>0) dp[i][j]=dp[i-1][j];
                else if(j>0) dp[i][j]=dp[i][j-1];
            }
        }        
        return dp[text1.size()-1][text2.size()-1];
    }
};