最长公共子序列

题目

分析

• $f[i][j]$表示$A$以$i$结尾，$B$以$j$结尾的公共子序列的集合

• 如果$a[i]==b[j]$，那么$f[i][j] = f[i-1][j-1] + 1$

• 如果$a[i] ! = b[j]$，那么有两种情况：

  • $a[i]$在最长公共子序列中，$b[j]$不在 $\rightarrow f[i][j-1]$
  • $b[j]$在最长公共子序列中，$a[i]$不在 $\rightarrow f[i-1][j]$
  • $a[i]$和$b[j]$都不在$\rightarrow f[i-1][j-1]$

  但是$f[i][j-1]$表示$b[j]$一定不在，$a[i]$可以在，可以不在，所以$f[i][j]$包含两个数都不在的情况。同理$f[i-1][j]$也是，所以我们只需要求这三个表达式的最大值即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> 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][j - 1], f[i - 1][j]);
            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;
}