思路
状态表示:
集合:所有A[1~i] 与 B[1 ~ j] 的公共子序列的集合(需要双重循环从1~i, 1~j枚举)
属性:最大值
(状态表示很重要,一定要搞懂!!!!!!要看清楚集合是什么!!不要乱了!!!)
状态计算
00:不包含$ai,bj$在$f[i][j]$ 最大公共序列中
01:不包含$ai$,包含$bj$
10:包含$ai$,不包含$bj$
11:$ai,bj$都包含
注意
不重不漏
不漏:分为四种状态(参考下图)
00:$f[i-1][j-1]$ 从定义可以看出,一定被$f[i-1][j]$ 或 $f[i][j-1]$ 包含,可不用带入计算
01:$f[i-1][j]$ 从定义看出,首先一定不包含ai,然后这种状态它既可能包含了$bj$和不含$bj$的情况, 但是不影响答案,求最大值重复也没关系,。
01:$f[i][j - 1]$同理,因此这两种状态一定存在
(将 $f[i-1][j]$ 与$f[i][j-1]$的最大值进行状态转移到$f[i][j]$中)
11:同时包含$ai,bj$,因为是公共序列,所以需要在满足$ai == bj $的前提下计算
$f[i-1][j-1] + 1$ , 在1 ~ i - 1
和 1 ~ j - 1
中选出最大值,再加上$ai(bj)$这个字母,长度加一
闫式DP:
代码
#include<iostream>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int main(){
int n, m;
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][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m] << endl;
return 0;
}