leetcode1143.最长公共子序列

leetcode1143.最长公共子序列

这是一道典型的两个数组的dp问题

状态表示

我们空可以根据经验+题目要求得出状态表示

dp[i][j] 表示：在 text1[0,i] 区间内以及 text2[0,j] 区间内的所有公共子序列中最长公共子序列的长度

状态转移方程

我们根据 text1 的 i 位置以及 text2 的 j 位置来分析问题

• 当 text1[i] == text2[j] 时， text 1与 text2 的公共子序列一定是以 i/j 这个位置为结尾的，因此我们只需要去 text1 的 [0,i-1] 与 text2 的[ 0,j-1] 区间内找所有公共子序列中最长公共子序列的长度，即 dp[i-1][j-1] ,在后面加一即可
• 当 text1[i] != text2[j] 时, text 1与 text2 的公共子序列一定不以 i/j 这个位置为结尾，此时我们需要去 text1 的 [0,i-1] 与 text2 的[ 0,j] 区间、 text1 的 [0,i] 与 text2 的[ 0,j-1] 区间以及 text1 的 [0,i-1] 与 text2 的[ 0,j-1] 区间内找，分别对应 dp[i-1][j] 、 dp[i][j-1] 、 dp[i-1][j-1] ，又因为第三个被前两个包含，所以只需求出前两个的最大值

if(s[i] == t[j])
    dp[i][j] = dp[i-1][j-1]+1;
else
    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

初始化

dp表多开一行、多开一列可以避免越界访问的问题，第零行表示 text1 是空串，因此最长公共子序列的长度为零，同理，第一列也全部为零

vector<vector<int>> dp(m+1,vector<int>(n+1));

填表顺序

从上到下，从左至右，并注意映射关系

返回值

dp[m][n]

完整代码

int longestCommonSubsequence(string s, string t) {
    int m = s.size(), n = t.size();
    vector<vector<int>> dp(m+1,vector<int>(n+1));

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