最长公共子序列(dp) & hdu 1159 Common Subsequence

最长公共子序列(dp) & hdu 1159 Common Subsequence

最长公共子序列问题（long conmon subsequence）简称

LCS。

来自《算法导论》的介绍：

我们将最后一种相似度的概念命名为最长公共子序列问题。一个给定序列的子序列，就是将给定 序列中零个或多个元索去掉之后得到的结果。其形式化定义如下：给定一个序列X=，另一个序列Z=满足如下条件时称为X的子序列(subsequence),即存在一个严格递增的X的下标序列,对所有j=1，2，…，k，满足xij=zj。例如，Z=的子序列，对应的下标序列为〈2, 3, 5, 7>。

给定两个序列X和Y,如果z既是x的子序列，也是y的子序列，我们称它是X和Y的公 共子序列（common subsequence)。例如，如果 X=〈，那么序列〈B，C，A〉就是X和Y的公共子序列。但它不是X和Y的最长公共子序 列(LCS),因为它长度为3,而〈B, C, B, A〉也是X和Y的公共子序列，其长度为4。〈B, C, B，A>是X和Y的最长公共子序列，也是，因为X和Y不存在长度大于等于5 的公共子序列。

LCS是具有

最优子结构的：

递推公式：

用动态规划联系递推公式来解决问题：

来实战吧：

hdu 1159 Common Subsequence

题目：​​#include#includeusing namespace std;const int maxn=505;int C[maxn][maxn],B[maxn][maxn];char s1[maxn],s2[maxn];int Lcslength(){ memset(C,0,sizeof(C)); memset(B,0,sizeof(B)); int i,j,length1=strlen(s1+1),length2=strlen(s2+1); for(i=1;i<=length1;i++){ for(j=1;j<=length2;j++){ if(s1[i]==s2[j]){ C[i][j]=C[i-1][j-1]+1; B[i][j]=1; //指向左上方 } else if(C[i-1][j]>=C[i][j-1]){ C[i][j]=C[i-1][j]; B[i][j]=2; //指向上面 } else { C[i][j]=C[i][j-1]; B[i][j]=0; //指向左边 } } } return C[length1][length2];}int main(){ //freopen("cin.txt","r",stdin); int i,j; while(scanf("%s%s",s1+1,s2+1)>0){ printf("%d\n",Lcslength()); memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); } return 0;}

当然，这道题只要求求出长度不用还原序列，所以我们可以不写B[][].

#include #include#includeusing namespace std;const int maxn=505;int C[maxn][maxn];char s1[maxn],s2[maxn];int Lcslength(){ memset(C,0,sizeof(C)); int i,j,length1=strlen(s1+1),length2=strlen(s2+1); for(i=1;i<=length1;i++){ for(j=1;j<=length2;j++){ if(s1[i]==s2[j]) C[i][j]=C[i-1][j-1]+1; else if(C[i-1][j]>C[i][j-1]) C[i][j]=C[i-1][j]; else C[i][j]=C[i][j-1]; } } return C[length1][length2];}int main(){ //freopen("cin.txt","r",stdin); int i,j; while(scanf("%s%s",s1+1,s2+1)>0){ // '>0'要写上哦 printf("%d\n",Lcslength()); memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); } return 0;}

这样有木有更简洁~~

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。