动态规划中的最长公共子序列

《动态规划中的最长公共子序列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.3最长公共子序列定义：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。找出{A,B,C,D}的所有子序列思考：有n个元素的序列至多有多少个子序列？2n（包括空）说“至多”是因为子序列可能相等（但具有不同下标序列）公共子序列定义：如果序列Z既是序列X的子序列又是序列Y的子序列，则称Z是X和Y的公共子序列。找出X=(A,B,C,D,A,B),Y=(B,D,C,A,B,A)的所有公共子序列。最长公共子序列找出X和Y的最长公共子序列。对于任意给定的X和Y，它们的最长公共子序列唯一吗？举例说明。不一定。如{A,B}与{B,

2、A}本节的问题是只找出一个最长公共子序列。最长公共子序列的结构设序列X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zk},则(1)若xm=yn,则Zk-1是Xm–1和Yn–1的最长公共子序列；如：X={…,C},Y={…,C},则Z={…,C}最长公共子序列的结构(续)(2)若xm≠yn,且zk≠xm，则Z是Xm–1和Y的最长公共子序列；如：X={…,C},Y={…,B},zk≠C,则在计算最长公共子序列时，可不考虑X的最后一个元素C最长公共子序列的结构(续)(3)若xm≠yn,且zk≠yn

3、，则Z是X和Yn–1的最长公共子序列如：X={…,C},Y={…,B},zk≠B,则在计算最长公共子序列时，可不考虑Y的最后一个元素B最长公共子序列的结构(续)两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，因此，最长公共子序列问题具有最优子结构性质。讨论可否根据序列的第1个元素来重述本问题？这样做有什么优缺点？可以。这样做不利于描述，如前面Xm–1可以方便地表示X前m–1个元素，改后就比较麻烦。从递归的角度来看，一般也是从后面增减元素。当xm=yn时，有一个子问题，即：找出Xm–1和Yn–1的最长公共子序列当

4、xmyn时，有两个子问题，即(1)找出Xm–1和Y的最长公共子序列，(2)找出X和Yn–1的最长公共子序列。而这两个子问题都包含了同一个子问题(Xm–1,Yn–1)。因此，本问题满足子问题重叠性质。问题分析令c[i][j]记录Xi和Yj的最长公共子序列的长度，则有0i=0,j=0c[i][j]=c[i-1][j-1]+1xi=yjmax{c[i][j-1],c[i-1][j]}xi≠yj问题分析(续)显然不应以递归方式（自顶向下，即先考虑最后一个字符）设计算法，而应设计动态规划算法，即从第一个字符开始考虑。问题分析(续)计算

5、最优值程序跟踪X={ACBD}Y={ABDA}cb00000011110111101222012330000001331022220213302213ijx[i]=y[j]c[i-1][j]>=c[i][j-1]11Y2N3N4Y21NY2NY补充习题1.X={B,C,A,D}Y={C,A,B,D},求X与Y的最长公共子序列，并画出数组c与b.cb00000000110111101222012230000002213013220213302221i:j:补充习题(答案)1.X={B,C,A,D}Y={C,A,B,D},求X与Y

6、的最长公共子序列，并画出数组c与b.cb00000000110111101222012230000002213013220213302221i:123j:123412341234讨论结构化与面向对象程序设计的联系与区别？面向对象的局部来看是结构化的。结构化的基本思想是“自顶向下，逐步求精”,面向对象的基本意图是提高软件模块的复用性。纯结构化的程序编译后基本上没有多余的代码，而面向对象的程序有许多。面向对象以机器的运行复杂度换取编程人员的编写复杂度。…