最长公共子序列问题
状态表示f[i][j] 集合：所有在第1个序列的前i个字母，和在第二个序列的前j个字母中出现的子序列，属性Max
状态计算：f[i - 1][j - 1] f[i - 1][j] f[i][j - 1] f[i - 1][j - 1] + 1
f[i - 1][j - 1]包含在f[i - 1][j] 和f[i][j - 1]中，f[i - 1][j]包含01 f[i][j - 1]包含10
这四种可能会重叠，但是求Max无关紧要

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];

int main(){
    scanf("%d%d",&n,&m);
    scanf("%s%s",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]);
            if(a[i] == b[j])    f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1);
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}