题解 | 最长公共子序列(一)

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1010;

int n, m;
char a[N], b[N];
int f[N][N];//f[i][j]表示a串前i个字符和b串前j个字符的最长公共子串

int main()
{
    cin>>n>>m;
    cin >> a+1 >> b+1;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(f[i-1][j], f[i][j-1]);//状态转移，这两个在一起还包含了f[i-1][j-1]的情况
            if(a[i]==b[j]) f[i][j]=max(f[i][j], f[i-1][j-1]+1);
        }
    
    cout<<f[n][m];
    
    return 0;
}

线性DP，集合表示就是a串的前i个字符和b串的前j个字符的最长公共自序列

时间复杂度O(N*M)

把状态不漏的转移一遍（中间有包含重复的，但是求max没事）

#牛客春招刷题训练营#