leetcode1143最长公共子序列

逃离我推掉我的手 2023-03-13 12:25 30阅读 0赞

## 最长公共子序列 ##

例
    "abc"
    "abc"
    count=3
    思想：dp[n][m]，动态规划
    dp[i][j]是str1[0~i]与str2[0~j]的最长公共子序列

d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j − 1 \] + 1 dp\[i\]==dp\[j\] m a x ( d p \[ i − 1 \] \[ j \] , d p \[ i \] \[ j − 1 \] ) dp\[i\]!=dp\[j\] dp\[i\]\[j\]= \\begin\{cases\} dp\[i-1\]\[j-1\]+1& \\text\{dp\[i\]==dp\[j\]\}\\\\ max(dp\[i-1\]\[j\],dp\[i\]\[j-1\])& \\text\{dp\[i\]!=dp\[j\]\} \\end\{cases\} dp\[i\]\[j\]=\{ dp\[i−1\]\[j−1\]\+1max(dp\[i−1\]\[j\],dp\[i\]\[j−1\])dp\[i\]==dp\[j\]dp\[i\]!=dp\[j\]

int send_value(int a)
        {
            if(a<0)
                return a+1;
            else   
                return a;
        } 
        int longestCommonSubsequence(string text1, string text2) {
            int len1=text1.size();
            int len2=text2.size();
            int dp[len1][len2];
            int i,j,count=0;
            if(len1==0||len2==0)
                return count;
            for(i=0;i<len1;i++)
                for(j=0;j<len2;j++)
                    dp[i][j]=0;
            for(i=0;i<len1;i++)//注意 我是从0开始的所以要考虑i-1<0，j-1<0的情况
                for(j=0;j<len2;j++)
                {
                    if(text1[i]==text2[j])
                    {
                        if(j-1<0||i-1<0)//一个字串0从开始 肯定为1
                            dp[i][j]=1;
                        else
                            dp[i][j]=dp[i-1][j-1]+1;
                    }
                    else
                        dp[i][j]=max(dp[send_value(i-1)][send_value(j)],dp[send_value(i)][send_value(j-1)]);//注意i-1<0，j-1<0
                       
                    count=max(count,dp[i][j]);
                }
            return count;
        }