根据y式dp分析法
分析
对于状态计算时的四种情况
00:子序列中不包含$a[i], b[j]$,$dp[i][j] = d[i - 1][j - 1]$
01:子序列中不包含$a[i]$,但包含$b[j]$, 但 $\pmb{d[i][j] \not= d[i - 1][j]}$ , 根据状态表示,$dp[i - 1][j]$ 为 a的前i- 1个字符和 b的前j- 1个字符的子序列,不一定包含$dp[j]$, 即 $dp[i - 1][j]$ 包含 01 因为所求的是最大值允许重复,可用$dp[i - 1][j]$ 来代替$dp[i][j]$
10: 同01
11:子序列中包含$a[i],b[j]$,这种情况成立当且仅当 $a[i] = b[j]$, $dp[i][j] = d[i - 1][j - 1] + 1$
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N];
char a[N], b[N];
int n, m;
int main()
{
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if(a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
cout << dp[n][m] << endl;
return 0;
}