题目#

分析#

• $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]$也是，所以我们只需要求这三个表达式的最大值即可。

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1010;
6

7
int n, m;
8
char a[N], b[N];
9
int f[N][N];
10

11
int main()
12
{
13
    cin >> n >> m;
14
    scanf("%s%s", a + 1, b + 1);
15

16
    for (int i = 1; i <= n; i ++ )
17
        for (int j = 1; j <= m; j ++ )
18
        {
19
            f[i][j] = max(f[i][j - 1], f[i - 1][j]);
20
            if (a[i] == b[j]) f[i][j] = max(f[i - 1][j - 1] + 1, f[i][j]);
21
        }
22

23
    cout << f[n][m] << endl;
24
    return 0;
25
}