leetcode1143.最长公共子序列

leetcode1143.最长公共子序列

最长公共子序列

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

状态表示

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

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

状态转移方程

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

• 当text1[i] == text2[j]时，text1与text2的公共子序列一定是以i/j这个位置为结尾的，因此我们只需要去text1的[0,i-1]与text2的[0,j-1]区间内找所有公共子序列中最长公共子序列的长度，即dp[i-1][j-1],在后面加一即可
• 当text1[i] != text2[j]时,text1与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];
}