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

1、3.3 最长公共子序列最长公共子序列n定义：一个给定序列的定义：一个给定序列的子序列子序列是在该序是在该序列中删去若干元素后得到的序列。列中删去若干元素后得到的序列。找出找出a, b, c, d的所有子序列的所有子序列思考：有思考：有n个元素的序列至多有多少个子序个元素的序列至多有多少个子序列？列？2n（包括空）（包括空）说说“至多至多”是因为子序列可能相等（但是因为子序列可能相等（但具有不同下标序列）具有不同下标序列）公共子序列公共子序列n定义：如果序列定义：如果序列z既是序列既是序列x的子序列又的子序列又是序列是序列y的子序列，则称的子序列，则称z是是x和和y的公的公共子序列。共子序列。n

2、找出找出x = (a, b, c, d, a, b), y = (b, d, c, a, b, a)的所有公共子序列。的所有公共子序列。最长公共子序列最长公共子序列n找出找出x和和y的最长公共子序列。的最长公共子序列。n对于任意给定的对于任意给定的x和和y，它们的最长公共，它们的最长公共子序列唯一吗？举例说明。子序列唯一吗？举例说明。n不一定。如不一定。如a, b与与b, an本节的问题是只找出一个最长公共子序本节的问题是只找出一个最长公共子序列。列。最长公共子序列的结构最长公共子序列的结构设序列设序列x=x1, x2, , xm, y=y1, y2, , yn, z=z1, z2, , zk

3、,则则(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，则，则z是是x和和yn 1的最

4、长公共子序列的最长公共子序列如：如：x = , c, y = , b, zk b, 则则在计算最长公共子序列时，可不考在计算最长公共子序列时，可不考虑虑y的最后一个元素的最后一个元素b最长公共子序列的结构最长公共子序列的结构(续续)n两个序列的最长公共子序列包含了两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序这两个序列的前缀的最长公共子序列，因此，最长公共子序列问题具列，因此，最长公共子序列问题具有最优子结构性质。有最优子结构性质。讨论讨论可否根据序列的第可否根据序列的第1个元素来重述本问个元素来重述本问题？这样做有什么优缺点？题？这样做有什么优缺点？可以。这样做不利于描述，如前

5、面可以。这样做不利于描述，如前面xm1可以方便地表示可以方便地表示x前前m 1 个元素，改个元素，改后就比较麻烦。从递归的角度来看，后就比较麻烦。从递归的角度来看，一般也是从后面增减元素。一般也是从后面增减元素。n当当xm = yn时，有一个子问题，即时，有一个子问题，即 ：找出：找出xm 1和和yn 1的最长公共子序列的最长公共子序列n当当xm yn时，有两个子问题，即时，有两个子问题，即 (1)找出找出xm 1和和y的最长公共子序列，的最长公共子序列， (2)找出找出x和和yn 1的的最长公共子序列。而这两个子问题都包含了最长公共子序列。而这两个子问题都包含了同一个子问题同一个子问题(xm

6、 1, yn1) 。 因此，本问题因此，本问题满足子问题重叠性质。满足子问题重叠性质。问题分析问题分析令令cij记录记录xi和和yj的最长公共子序列的长度，的最长公共子序列的长度，则有则有 0 i = 0, j = 0cij = ci - 1j - 1 + 1 xi = yj maxcij - 1 , ci - 1j xi yj问题分析问题分析(续续)n显然不应以递归方式（自顶向下，即先考虑显然不应以递归方式（自顶向下，即先考虑最后一个字符）设计算法，而应设计动态规最后一个字符）设计算法，而应设计动态规划算法，即从第一个字符开始考虑。划算法，即从第一个字符开始考虑。问题分析问题分析(续续)计算

7、最优值计算最优值程序跟踪程序跟踪x = a c b d y = a b d a c b00000011110111101222012330000001331022220213302213ijxi=yj ci-1j=cij-111y2n3n4y21ny2ny补充习题补充习题n1. x=b, c, a, d y=c, a, b, d,求x与y的最长公共子序列，并画出数组c与b. c b00000000110111101222012230000002213013220213302221i:j:补充习题补充习题(答案答案)n1. x=b, c, a, d y=c, a, b, d,求x与y的最长公共子序列，并画出数组c与b. c b00000000110111101222012230000002213013220213302221i: 1 2 3j: 1 2 3 4 1 2 3 4 1 2 3 4讨论讨论结构化与面向对象程序设计的联系与区别？结构化与面向对象程序设计的联系与区别？面向对象的局部来看是结构化的。面向对象的局部来看是结构化的。结构化的基本思想是结构化的基本思想是“自顶向下，逐步求精自顶向下，逐步求精”,面向对象的基本意图是提高软件模块的面向对象的基本意图是提高软件模块的复用性