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

集合：所有A[1-i]、B[1-j]的公共子序列二集合

属性：max

状态：1. 子序列不包含ai 不包含bj => f[i - 1][j - 1]（去除）

2. 不包含ai 包含bj => f[i - 1][j]

3. 包含ai 不包含bj => f[i][j - 1]

4. 包含ai 包含bj => f[i - 1][j - 1] + 1

会有重复 但会全部覆盖

最后归为两类 一个是 当a末尾= b末尾时 f[i - 1][j - 1] + 1 第二个是maxmax(f[i - 1][j], f[i][j - 1])

#include <iostream>
using namespace std;

const int N = 1010;
char a[N], b[N];
int f[N][N];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= m; i ++) cin >> b[i];
    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] << endl;
    return 0;
}