$\LARGE\color{orange}{刷题日记(算法提高课)}$

$f[i][j]$ 表示的集合为以 $A[0\sim i]$ 和 $B[0\sim j]$ 所构成的公共子序列，属性为所有公共子序列当中最长的

对于 $f[i][j]$ 表示的集合，我们以 $A[i]$ 与 $B[j]$ 是否相等为划分依据

• 若二者相等，那么 $f[i][j]$ 的值为同时减去 $A[i]$ 和 $B[j]$ 之后再加一，即 $f[i][j]\ =\ f[i\ -\ 1][j\ -\ 1]\ +\ 1$

• 若二者不相等，此时 $A[i]$ 有可能会跟 $B[0\sim j]$ 构成更长的公共子序列，同理 $B[j]$ 也有可能跟 $A[0\sim i]$ 构成更长的公共子序列，因此需要二者取较大值，即 $f[i][j]\ =\ max(f[i\ -\ 1][j],\ f[i][j\ -\ 1])$

字符串从下标为 1 开始存取会更方便

下面给出一般性的思路：

我们可以对 $A[i]$ 和 $B[j]$ 是否在公共子序列当中进行讨论，这也因此可以分出四种情况

• 若 $A[i]$ 和 $B[j]$ 均在公共子序列当中，有 $f[i][j]=f[i-1][j-1]$

• 若 $A[i]$ 在，$B[j]$ 不在，有 $f[i][j]=f[i][j-1]$

• 若 $A[i]$ 不在，$B[j]$ 在，有 $f[i][j]=f[i-1][j]$

• 若 $A[i]$ 和 $B[j]$ 均不在，这与情况二和三重合了

因此我们对上面的三个式子取最大值即可

完整代码：

#include <iostream>

using namespace std;

const int N = 1010;

char a[N], b[N];
int f[N][N];
int n, m;

int main()
{
    cin >> n >> m >> 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);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}