最长公共子序列

给定两个长度为 N 和 M的字符串 A 和 B，求既是 A 的子序列又是 B
 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N
 和 M
。

第二行包含一个长度为 N
 的字符串，表示字符串 A
。

第三行包含一个长度为 M
 的字符串，表示字符串 B
。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤1000

输入样例：

4 5
acbd
abedc

输出样例：

3

难懂的地方在于maxv
maxv的含义是，在a字符串中选取前i-1个，b字符串中选取前j-1个，并且以b字符串中第j-1个字符结尾，这样情况下最长公共子序列的长度

我们状态转移的时候， 每次新读入a中一个字母，然后我们想，如果b中也有一个字母和它相同，那么就可以以这个字母作为一个公共子序列的结尾

我们去看看b中取这个字母以前，a中也取这个字母以前的最长公共子序列有多长
那么以这个字母作为结尾的话，公共子序列长度加一即可

突然想到，那这样的话当然也可以用滚动数组做啦

常规

#include<bits/stdc++.h>

using namespace std;

const int N = 1117;
int n, m, f[N][N], res;
char a[N], b[N];

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;
    for(int i = 1; i <= n; i ++)
    {
        int maxv = 0;
        for(int j = 1; j <= m; j ++)
        {
            maxv = max(maxv, f[i-1][j-1]);
            if(a[i] == b[j]) f[i][j] = maxv + 1;
            else f[i][j] = f[i-1][j];
        }
    }
    for(int i = 1; i <= m; i ++) res = max(res, f[n][i]);
    cout << res;
}

滚动数组

#include<bits/stdc++.h>

using namespace std;

const int N = 1117;
int n, m, f[2][N], res, t;
char a[N], b[N];

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;
    for(int i = 1; i <= n; i ++)
    {
        int maxv = 0;
        for(int j = 1; j <= m; j ++)
        {
            maxv = max(maxv, f[t^1][j-1]);
            if(a[i] == b[j]) f[t][j] = maxv + 1;
            else f[t][j] = f[t^1][j];
        }
        t ^= 1;
    }
    for(int i = 1; i <= m; i ++) res = max(res, f[t^1][i]);
    cout << res;
}