题目链接： https://leetcode.cn/problems/longest-common-subsequence/

TLE

暴力递归+记忆化版本（基于字符串长度无优化版本）//注意text1[i1-1]==text2[i2-1]

class Solution {
public:
    int dp[1000][1000];
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        memset(dp,-1,sizeof(dp));
        return f(dp,text1,text2,n,m);
    }
    int f(int dp[][1000],string t1,string t2,int i1,int i2){
        //basecase
        if(dp[i1][i2]!=-1)return dp[i1][i2];
        if(i1==0||i2==0){
            dp[i1][i2]=0;
            return 0;
        }
        try(四种不同可能性）
        int p1=f(dp,t1,t2,i1-1,i2);
        int p2=f(dp,t1,t2,i1-1,i2-1);
        int p3=f(dp,t1,t2,i1,i2-1);
        int p4= t1[i1-1]==t2[i2-1]? p2+1: p2;

        int big=max(max(p1,p2),max(p3,p4));
        dp[i1][i2]=big;
        return dp[i1][i2];

    }
};

暴力递归+记忆化（基于字符串长度的优化版本）(感觉上是能通过的，但其实没有）

class Solution {
public:
    int dp[1005][1005];
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        memset(dp,-1,sizeof(dp));
        return f(dp,text1,text2,n,m);
    }
    int f(int dp[][1005],string t1,string t2,int i1,int i2){
        if(dp[i1][i2]!=-1)return dp[i1][i2];
        if(i1==0||i2==0){
            dp[i1][i2]=0;
            return 0;
        }
        if(t1[i1-1]==t2[i2-1]){
            dp[i1][i2]=f(dp,t1,t2,i1-1,i2-1)+1;
            return dp[i1][i2];
        }else{
            dp[i1][i2]=max(f(dp,t1,t2,i1-1,i2),f(dp,t1,t2,i1,i2-1));
            return dp[i1][i2];
        }
    }
};

二维DP

普通版本

class Solution {
public:
    int dp[1005][1005];
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size();
        int m=text2.size();
        memset(dp,0,sizeof(dp));

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m;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[n][m];
    }

};

状压版本

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