1143. 最长公共子序列

1. 背

这道题和最长回文子串类似，dp[i][j]表示 text1[0:i] 和 text2[0:j]的最长公共子序列的长度
只不过最长回文子串是针对一个字符串的，这个是针对两个字符串的。
状态转移方程是不是也和回文子串非常相似。

创建数组的时候多一位，就是(m+1,n+1)的数组，其中第0行和第0列都是0，因为0字符串和text的几位放一起都是0。

2. 答案

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m =static_cast(text1.length()),n=static_cast(text2.length());
        vector> dp(m+1,vector(n+1,0));
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=n;++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];

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19