最长公共子序列

解题思路:模板题，力扣1143. 最长公共子序列

假设字符串 text1和 text2的长度分别为 m 和 n,创建 m+1 行 n+1 列的二维数组 dp,其中 dp[i][j]表示 text1[0:i]和 text2[0:j]的最长公共子序列的长度.

1 当 text1[i-1]==text2[j-1]时,将这两个相同的字符称为公共字符,考虑text1[0:i-1]和text2[0:j-1]的最长公共子序列,再增加一个字符(即公共字符)即可得到 text1[0:i]和 text2[0:j]的最长公共子序列，因此 dp[i][j]=dp[i-1][j-1]+1.

2 当 text1[i-1]!=text2[j-1]时,考虑以下两项:

text1[0:i-1]和 text2[0:j]的最长公共子序列;

text1[0:i]和text2[0:j-1]的最长公共子序列。

要得到text1[0:i]和text2[0:j]的最长公共子序列,应取两项中的长度较大的一项,因此 dp[i][j]=max(dp[i-1][j],dp[i][j-1]).

参考代码:

#include<bits/stdc++.h>
using namespace std;
int longestCommonSubsequence(string text1, string text2) {
    int n = text1.length();
    int m = text2.length();
    int dp[n+1][m+1];
    memset(dp,0,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        char c1 = text1[i-1];
        for(int j=1;j<=m;j++){
            char c2 = text2[j-1];
            if(c1 == c2){
                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];
}
int main()
{
    string s1,s2;
    cin>>s1;
    cin>>s2;
    cout<<longestCommonSubsequence(s1,s2)<<endl;
    return 0;
}