代码

#include <bits/stdc++.h>

using namespace std;
int f[5010][5010];
char a[10000];
char b[10000];
int main()
{
    int n;
    cin>>n;
    cin>>a+1;
    int m;
    cin>>m;
    cin>>b+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i]==b[j])
                f[i][j]=f[i-1][j-1]+1;
            else
                f[i][j]=max(f[i-1][j],f[i][j-1]);
    cout<<f[n][m];
    return 0;
}

核心

DP