题目描述

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

算法

(动态规划) $O(n^2)$

设 f[i][j] 为A串前i项与B串前j项的最大公共子序列长度。
将f[i][j]划分为 a[i]与b[j] 是否包含在最大公共子序列中
则有
00: 都不是构成最大公共子序列的字母。 退化为 f[i-1][j-1]
01: a[i]不是 b[j]是。 该情况是 f[i-1][j]中的11或01，所以其值<=f[i-1][j]，又因为f[i-1][j]<=f[i][j],所以可以进行max操作。
10: a[i]是 b[j]不是。 同理可用f[i][j-1]代替（注意f[i][j-1]>= 10的值)
11: 都是。 当a[i]==b[j]时，相当于在f[i-1][j-1]的最大公共子序列中再加入一个字母，所以是f[i-1][j-1] + 1。 而a[i]!=b[j]时，与最长公共子序列最后一个字母相同产生矛盾。

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n, m, f[N][N];
char a[N], b[N];
int main(){
    cin >> n >> m;
    cin >> 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 - 1][j - 1] + 1, f[i][j]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}