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

1、动态规划解最长公共子序列 一、 问题描述与分析经常遇到一些复杂的问题，有时我们将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。由于分解到的子问题往往不是独立的，用一个表来记录所有已解决的子问题的答案，这样就得到了原问题的解，这就是动态规划法的基本思想。一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z即是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。在公共子序列中长度最长的则是最长公共子序列。穷举搜索法是最容易想到的解题算法。对X的所有子序列，检查它是否也是Y的子序列，从而确定它是否是X和Y的公共子序列。并且

2、在检查过程中记录最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。事实上，最长公共子序列问题具有最优子结构的结构性质。二、 算法设计1. 最长公共子序列的结构设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则1) 若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列；2) 若xmyn 且zkxm，则Z是Xm-1和Y的最长公共子序列；3) 若xmyn 且zkyn，则Z是X和Yn-1的最长公共子序列。其中，Xm-1=x1,x2,xm-1; Yn-1=y1,y2,yn-1; Zk-1=z1,z2,zk-1。证

3、明： 1) 用反证法。若zkxm，则z1,z2,zk,xm是X和Y的长度为k+1的公共子序列。这与Z是X和Y的最长公共子序列矛盾。因此，必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的长度为k-1的公共子序列。若Xm-1和Yn-1有长度大于k-1的公共子序列W，则将xm加在其尾部产生X和Y的长度大于k的公共子序列。此为矛盾。故Zk-1是Xm-1和Yn-1的最长公共子序列。2) 由于zkxm，Z是Xm-1和Y的公共子序列。若Xm-1和Y有长度大于k的公共子序列W，则W也是X和Y的长度大于k的公共子序列。这与Z是X和Y的最长公共子序列矛盾。由此即知，Z是Xm-1和Y的公共子序列。3)

4、证明与（2）类似。2. 子问题的递归结构由最长公共子序列的问题的最优子结构可知，当xm=yn时，找出是Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的最长公共子序列。当xmyn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。首先建立子问题最优值的递归关系。用Cij记录序列Xi和Yj的最长公共子序列的长度。其中Xi=x1,x2,xm；Yj=y1,y2,yn。当i=0或j=0时，空序列是Xi和Yj的最长公共子序

5、列，故此时Cij=0。在其他情况下，由最优子结构性质可建立递归关系如下：Cij= 0 i=0，j=0 ci-1j-1+1 i，j>0；xi =yj maxcij-1，ci-1j i，j>0；xi yj 3. 例子：求两字符序列的最长公共字符子序列问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=x1,x2,xm，序列Y=y1,y2,yn是X的子序列，存在X的一个严格递增下标序列i0，i1，ik-1，使得对所有的j=0，1，k-1，有xi=yj。例如，X=“BACDCA”，Y=“ABDCA”是X

6、的一个子序列。考虑最长公共子序列问题如何分解成子问题，设A=a0，a1，am-1，B=b0，b1，bm-1，并Z=z0，z1，zm-1为它们的最长公共子序列。不难证明有以下性质：1) 如果am-1=bn-1，则若zk-1=am-1=bn-1，得z0，z1，zm-1是a0，a1，am-1和b0，b1，bm-1的一个最长公共子序列；2) 如果am-1bn-1，则若zk-1am-1，得z0，z1，zm-1是a0，a1，am-2和b0，b1，bm-1的一个最长公共子序列；3) 如果am-1bn-1，则若zk-1bn-1，得z0，z1，zm-1是a0，a1，am-1和b0，b1，bm-2的一个最长公共子

7、序列。这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找a0，a1，am-1和b0，b1，bm-1的一个最长公共子序列；如果zk-1bn-1，则要解决两个子问题，找出a0，a1，am-2和b0，b1，bm-1的一个最长公共子序列和找出a0，a1，am-1和b0，b1，bm-2的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。引进一个二维数组cij，用cij记录Xi与Yj的LCS 的长度，bij记录 cij，是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算cij之前，ci-1j-1，ci-j与cij-1均已计算

8、出来。此时我们根据xi=yj还是xiyj，就可以计算出cij。回溯输出最长公共子序列过程：jABDCAi000000B00211131313A01112121221C01212122122D01212212222C01212223133A01112223241则输出结果为：BDCA由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Om+n。4. 得出算法：计算最优化：cij存储Xi与Yj的最长公共子序列的长度，bij记录 cij的值是由那一个子问题得到的。问

9、题的最优值，即X和Y的最长公共子序列的长度记录于cmn中。void LcsLength(char x, char y, int m, int n, int c, int b) for(int i = 0; i <= m; i+)ci0 = 0; for(int j = 1; j <= n; j+)c0j = 0;for(i = 1; i<= m; i+)for(j = 1; j <= n; j+) if(xi-1 = yj-1) cij = ci-1j-1 + 1; bij = 1; else if(ci-1j >= cij-1) cij = ci-1j; bij

10、 = 2; else cij = cij-1; bij = 3; 在算法Lcslength中，由于每个数组单元的计算耗费O1,故算法耗时Omn。构造最长公共子序列：从bmn开始，依其值在数组b中搜索。当bij=1时，表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上xi所得到的子序列；当bij=2时，表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同；bij=3时，表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。void LCS(int b, char x, int i, int j) if(i = 0 | j = 0) retu

11、rn; if(bij = 1) LCS(b, x, i-1, j-1); printf("%c", xi-1); else if(bij = 2) LCS(b, x, i-1, j); else LCS(b, x, i, j-1);在算法LCS中，每一次递归调用使i或j减1，因此算法的计算时间为Om+n。三、 算法实现#include <stdio.h>#include <string.h>void LCSLength(char x20, char y20, int m, int n, int c2020, int b2020) int i,j; f

12、or(i = 0; i <= m; i+) ci0 = 0; for(j = 1; j <= n; j+) c0j = 0; for(i = 1; i<= m; i+) for(j = 1; j <= n; j+) if(xi-1 = yj-1) cij = ci-1j-1 + 1; bij = 1; else if(ci-1j >= cij-1) cij = ci-1j; bij = 2; else cij = cij-1; bij = 3; void LCS(int b2020, char x20, int i, int j) if(i = 0 | j = 0

13、) return; if(bij = 1) LCS(b, x, i-1, j-1); printf("%c", xi-1); else if(bij = 2) LCS(b, x, i-1, j); else LCS(b, x, i, j-1);int main() char x20,y20;printf("请输入第一组序列： "); gets(x);printf("请输入第二组序列： ");gets(y); int b2020,c2020; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); LCS(b, x, m, n); printf("n长度为：%dn",cmn); return 0;四、 算法分析与改进在算法Lcslength中，由于每个数组单元的计算耗费O1,故算法耗时Omn。在算法LCS中，每一次递归调用使i或j减1，因此算法的计算时间为Om+n。算法可以进一步改进：在算法Lcslength和Lcs中，可进一步将数组b省去。对于数组cij，可以不借助于数组b而仅借助于c本身，在O1时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。因此，可以写一个类