(题目请点上面的原题链接)
分析
状态表示:f[i][j]: 所有A[1~i]和B[1~j]的公共子序列的集合中,子序列长度的最大值
状态计算:f[i][j]表示的集合可以按照子序列是否包括A[i]或B[j]
分成四类(满足不重不漏的划分原则)
假定子序列含有A[i]且含有B[j]记为11,则四个子集:
-
00 :相当于所有A[1~i-1]和B[1~j-1]的公共子序列的集合,即
f[i-1][j-1]
-
01 :中间两个比较坑,很容易就写成
f[i-1][j]
,但重新分析一下集合的含义就知道,这一表示只是说B从1~j中选,所以这个集合又可以分成两个小集合:包含B[j]的和不包含B[j]的。当前集合需要的是包含B[j]的这一小集合,可是我们没办法找到相应的表示,但是我们任然可以用f[i-1][j]
来表示我们的集合 —— 求最大值可以重但不能漏,我们用f[i-1][j]
所表示的更大的集合来覆盖掉当前01
这个小集合(下面10也同理),00 01 10 11
四个小集合的最大值是f[i][j],现在其中的01 10
用了更大的集合去表示,无非是多了一些重复部分而已,总的部分还是可以完全覆盖f[i][j]
所表示的集合,这就是为什么想当然的写了f[i-1][j]
也能AC的原因 -
10 :
f[i][j-1]
理由同上 -
11 :表示子序列既包含A[i]也包含B[j],由于是公共子序列,那么等于是说A[i]==B[j],所以这个集合并不一定存在,当A[i]==B[j]时,A中子序列包含A[i]定了,B中子序列包含B[i]定了,前面变化的部分的公共子序列最大长度在加上不变部分的一个就是
f[i-1][j-1] + 1
,
图:(求范围内的最大值,可重不可漏)
这样下来,我们发现状态f[i-1][j-1]
完全包含在f[i-1][j]
或f[i][j-1]
内的,也就是扩充后的10 01
已经把00
的情况给覆盖住了,所以考虑后三种情况即可
C++代码
- 若代码中涉及到类似于数组下标
i-1
,考虑一下数组从1开始存,方便一些
#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
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]); //10 01两种情况一定有
if(a[i]==b[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1); //a[i]==b[j]时再考虑11这种情况
}
cout<<f[n][m]<<endl;
return 0;
}