资源描述：
《动态规划解最长公共子序列.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
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)若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；3)若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。其中，Xm-1=x1,x2,…,xm-1;Yn-1=y1,y2,…,yn-1;Zk-1=z
3、1,z2,…,zk-1。证明：1)用反证法。若zk≠xm，则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)由于zk≠xm，Z是Xm-1和Y的公共子序列。若Xm-1和Y有长度大于k的公共子序列W，则W也是X和Y的长度大于k的公共子序列。这与Z是X和Y的最长公共子序列矛盾。由此即知
4、，Z是Xm-1和Y的公共子序列。3)证明与（2）类似。2.子问题的递归结构由最长公共子序列的问题的最优子结构可知，当xm=yn时，找出是Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。首先建立子问题最优值的递归关系。用Cij记录序列Xi和Yj的最长公共子序列的长度。其中Xi=x1,x2,…,xm；Yj=y1,y2,…,yn。
5、当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故此时Cij=0。在其他情况下，由最优子结构性质可建立递归关系如下：Cij=0i=0，j=0ci-1j-1+1i，j>0；xi=yjmaxcij-1，ci-1ji，j>0；xi≠yj1.例子：求两字符序列的最长公共字符子序列问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=x1,x2,…,xm，序列Y=y1,y2,…,yn是X的子序列，存在X的一个严格递增下标序列i0，i1，…，ik-1，使得对所有的j=0，1，…，k-1，有xi=yj。例如
6、，X=“BACDCA”，Y=“ABDCA”是X的一个子序列。考虑最长公共子序列问题如何分解成子问题，设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-1≠bn-1，则若zk-1≠am-1，得z0，z1，…，zm-1是a0，a1，…，am-2和b0，b1，…，bm-1的一个最长公共子序列；3)如果am-1≠bn-1，则若zk-1≠
7、bn-1，得z0，z1，…，zm-1是a0，a1，…，am-1和b0，b1，…，bm-2的一个最长公共子序列。这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找a0，a1，…，am-1和b0，b1，…，bm-1的一个最长公共子序列；如果zk-1≠bn-1，则要解决两个子问题，找出a0，a1，…，am-2和b0，b1，…，bm-1的一个最长公共子序列和找出a0，a1，…，am-1和b0，b1，…，bm-2的一个最长
