动态规划解最长公共子序列

动态规划解最长公共子序列一、 问题描述与分析经常遇到一些复杂的问题，有时我们将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。由于分解到的子问题往往不是独立的，用一个表来记录所有已解决的子问题的答案，这样就得到了原问题的解，这就是动态规划法的基本思想一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y,当另一序列Z即是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。在公共子序列中长度最长的则是最长公共子序列。穷举搜索法是最容易想到的解题算法。对X的所有子序列，检查它是否也是Y的子序列，从而确定它是否是X和Y的公共子序列。并且在检查过程中记录最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。事实上，最长公共子序列问题具有最优子结构的结构性质。二、 算法设计1.最长公共子序列的结构设序列和的最长公共子序列为，则1)若，则 ，且是 和 的最长公共子序列；2)若且 ，则是和的最长公共子序列；3)若且 ，则是和的最长公共子序列。其中，;;。证明：1)用反证法。若 ，则是和的长度为k+1的公共子序列。这与是和的最长公共子序列矛盾。因此，必有 。由此可知是和的长度为k-1的公共子序列。若和有长度大于k-1的公共子序列，，则将加在其尾部产生和的长度大于k的公共子序列。此为矛盾。故是和的最长公共子序列。2） 由于 ，是和的公共子序列。若 和有长度大于k的公共子序列，则也是和的长度大于k的公共子序列。这与是和的最长公共子序列矛盾。由此即知，是和的公共子序列。3） 证明与（2）类似。2.子问题的递归结构由最长公共子序列的问题的最优子结构可知，当 时，找出是和的最长公共子序列，然后在其尾部加上 即可得和的最长公共子序列。当 时，必须解两个子问题，即找出和的一个最长公共子序列及和的一个最长公共子序列。这两个公共子序列中较长者即为和的最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。首先建立子问题最优值的递归关系。用记录序列和的最长公共子序列的长度。其中； 。当i=0或j=0时，空序列是和的最长公共子序列，故此时 。在其他情况下，由最优子结构性质可建立递归关系如下：

3.例子：求两字符序列的最长公共字符子序列问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列，序列是的子序列，存在的一个严格递增下标序列，，，，使得对所有的，，， ，有 。例如，=“BACDCA”，=“ABDCA”是的一这样，在找A这样，在找A和B的公共子序列时，如有，则进一步解决一个子问题，找，， ， I，， ， IM J J ，要解决两个子问题，找出，，和找出，，，和，者作为A和B的最长公共子序列。的一个最长公共子序列；如果 ，则和， ， ， 的一个最长公共子序列的一个最长公共子序列，再取两者中较长引进一个二维数组，用记录与的LCS的长度，引进一个二维数组，用记录与的LCS的长度，记录，是通个子序列。考虑最长公共子序列问题如何分解成子问题，设 ， ， ， ，，，，，并，，，为它们的最长公共子序列。不难证明有以下性质：1）如果，则若，得，，，是，，，和， ， ，的一个最长公共子序列；2）如果，则若，得， ， ， 是， ，，和，， ， 的一个最长公共子序列；3）如果 ，则若 ，得， ， ，是和，， ， 的一个最长公共子序列。过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算 之前，均已计算出来。此时我们根据还是，就可以计算出则输出结果为：BDCA由于每次调用至少向上或向左(或向上向左同时)移动一步，故最多调用(m+n)次就会遇到i=0或j=0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为 。4.得出算法：计算最优化：存储与的最长公共子序列的长度， 记录的值是由那一个子问题得到的。问题的最优值，即和的最长公共子序列的长度记录于中。voidLcsLength(charx[],chary[],intm,intn,intc[][],intb[][]){for(inti=0;i<=m;i++)c[i][0]=0;for(intj=1;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(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]=3;在算法Lcslength中，由于每个数组单元的计算耗费，故算法耗时 。构造最长公共子序列:从 开始,依其值在数组b中搜索。当=1时，表示和的最长公共子序列是由和 的最长公共子序列在尾部加上所得到的子序列；当=2时，表示和的最长公共子序列与和的最长公共子序列相同； =3时，表示和的最长公共子序列与和 的最长公共子序列相同。voidLCS(intb[][],charx[],inti,intj){if(i==0||j==0)return;if(b[i][j]==1){LCS(b,x,i-1,j-1);printf("%c",x[i-1]);}elseif(b[i][j]==2)LCS(b,x,i-1,j);elseLCS(b,x,i,j-1);}在算法LCS中，每一次递归调用使i或j减1,因此算法的计算时间为 。三、算法实现#includevstdio・h>#include<string・h>voidLCSLength(charx[20],chary[20],intm,intn,intc[20][20],intb[20][20]){inti,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++)•[ozlEozlalozKozlqwif(A)s)a3J(..:昨场二馭W鼬)卯!Jdf(x)s)3SJ(..:P^^W-MYWM..)Wu!jd蚀]A'[0Z]xjeqo}Ouieui)ui?(l-rrx^qjsoiasp爼T-「x^qJSDl(Z==[f][!]qU!asp{?(【l-!】x/.P%ll)WU!JdWfT-!^qJSDl}(T==[f][!]qU!fujn)sj(0==flI0==阳！}(f1UI#!1UI*[oz]xjeqsWIEOZlq1U0S31piOA纶=【n【!】qWf]【!P=[0[>]9}asp{空=【n【!lq?【n【「!p=[n[>]9}([T-n[!]3=<[(][「!】圳!BS|a{代=【n【!】q代+[T-n[T->]3=[0[!]9}([T-[]A==[T-!]xU!}(++[他=>f=fpoiintm,n;m=strlen(x);n=strlen(y);LCSLength(x,y,m,n,c,b);LCS(b,x,m,n);printf("\n长度为：%d\n",c[m][n]);return0;}四、算法分析与改进在算法Lcslength中，由于每个数组单元的计算耗费 ，故算法耗时在算法LCS中，每一次递归调用使i或j减1,因此算法的计算时间为算法可以进一步改进：在算法Lcslength和Lcs中，可进一步将数组b省去。对于数组，可以不借助于数组b而仅借助于c本身，在 时间内确定的值是由， 和 中哪一个值所确定的。因此，可以写一个类似于Lcs的算法，不用数组b而在 时