AcWing 897. 最长公共子序列（LCS朴素版）

题目连接

https://www.acwing.com/problem/content/899/

思路

我们定义 f [ i ] [ j ] f[i][j] f[i][j]表示的是a串中长度为i和b串长度为j的最长公共子序列长度，那么我们当前匹配到的a[i]和b[j]如果相等 f [ i ] [ j ] f[i][j] f[i][j]的值一定是从 f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i−1][j−1]转移过来的，即 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + 1 f[i][j]=f[i-1][j-1]+1 f[i][j]=f[i−1][j−1]+1，否则的话我们就要从i-1的长度和j-1的长度中选择一个较好的情况即 f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) f[i][j] = max(f[i-1][j],f[i][j-1]) f[i][j]=max(f[i−1][j],f[i][j−1])

代码

#include
using namespace std;

const int N = 1e3+10;
int n,m;
int f[N][N];//f[i][j]表示的是a串中长度为i和b串长度为j的最长公共子序列长度
char a[N],b[N];

int main()
{
    cin>>n>>m;
    cin>>(a+1)>>(b+1);
    for(int i = 1;i