最长公共子序列–详解
难点:集合的划分
dp问题--->状态表示f[i,j]--->集合:所有在第一个序列的前i个字母且在第二个序列的前j个字母中出现的子序列。
---->属性:集合里面所有这些子序列长度的最大值MAX
--->状态计算:左边0代表a[i]右边0代表b[i],00,01,10,11.有四种状态
--->00=f[i-1,j-1]
--->11=f[i-1,j-1]+1
--->01=f[i-1,j]有重复
--->10=f[i,j-1]有重复
一般只有右三种情况,00包含在其他三种当中。
算法1
展开看,就是用一个n乘m的矩阵,把所有的结果遍历了一遍,每一次从a中选一个和b中的比较,若相同就+1,递推到最后fnm就是最大的长度。
C++ 代码
#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()
{
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++)
{
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);//当ai和bj相等才有第三种情况
}
printf("%d",f[n][m]);
return 0;
}