第3章动态规划法

1、算法设计与分析1第三章动态规划学习要点学习要点理解动态规划算法的概念。掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质理解动态规划算法与贪心算法的差异掌握设计动态规划算法的步骤。通过下面的应用范例学习动态规划算法设计策略（1）最短路径（2）矩阵连乘（3）凸多边形最优三角剖分（4）最长公共子序列算法设计与分析2算法设计与分析3问题的分解 n将待求解问题分解为若干子问题，通过子问题的解得到原问题的解，这是问题求解的有效途径。但是如何实施分解？n分治策略的基本思想是将规模为n的问题分解为k个规模较小的子问题，各子问题相互独立但与原问题求解策略相同。并不是所有问题都可以这样处理。

2、n问题分解的另一个途径是将求解过程分解为若干阶段（级），依次求解每个阶段即得到原问题的解。通过分解得到的各子阶段不要求相互独立，但希望它们具有相同类型，而且前一阶段的输出可以作为下一阶段的输入。这种策略特别适合求解具有某种最优性质的问题。n贪心法属于这类求解策略：对问题P(n)，其求解过程中各贪心选择步骤构成决策序列D=。Di的最优性仅依赖于D1,D2,.Di-1。贪心法不保证决策序列D最后求出解的最优性。算法设计与分析4动态规划 n动态规划也是一个分阶段判定决策过程，其问题求解策略的基础是决策过程的最优原理：为达到某问题的最优目标T，需要依次作出决策序列D=。如果D是最优的，则对任意i(1i

3、k)，决策子序列Di+1,Dk也是最优的，即当前决策的最优性取决于其后续决策序列的是否最优。由此追溯至目标，再由最终目标决策向上回溯，导出决策序列 D=，因此动态规划方法可以保证问题求解是全局最优的。n也可以这样理解：如果求最优解的问题可以划分成若干段（级），那么最后求得的最优解是由各个部分解所组成，而这些部分解一定是对应阶段的最优解。算法设计与分析5最短路径 n给定简单有向连通赋权图G=，w(i,j)是G中边的权。顶点集V可以划分为k+1个两两不交的子集Vi，i =0,1,2,.k。其中V0=s，Vk=t。对G中任一边，存在Vi、Vi+1，使得u属于Vi，v属于Vi+1，其中0ik。称G为k

4、段图，s点为起点，t为终点。n在G中求s出发到t的最短路径。这里最短是指s到t的路径上各边权的和最小。 算法设计与分析6一个多段图例子 记D(u,v)是G中起点为u,终点为v的最短路径，C(u,v)是该路径上各边权的和。设D(s,t)= ，vir属于Vr（r=1,2.k-1），则D(vi1,t)= 是从vi1出发到t的最短路径，D(vi2,t)= 是从vi2出发到t的最短路径等等。设u属于Vi，有：C(u,t)=minw(u,v)+C(v,t) (4.1) vVi+1 阶段4: C(7,t)=w(7,t)=8，C(8,t)=w(8,t)=4阶段3: C(4,t)=minw(4,7)+C(7,t

5、), w(4,8)+C(8,t)=12 C(5,t)=minw(5,7)+C(7,t), w(5,8)+C(8,t)=10 C(6,t)=minw(6,7)+C(7,t), w(6,8)+C(8,t)=8阶段2: C(1,t)=minw(1,4)+C(4,t), w(1,5)+C(5,t)=19 C(2,t)=minw(2,4)+C(4,t), w(2,5)+C(5,t), w(2,6)+C(6,t)=17 C(3,t)=minw(3,5)+C(5,t), w(3,6)+C(6,t)=13阶段1: C(s,t)=minw(s,1)+C(1,t), w(s,2)+C(2,t), w(s,3)+C

6、(3,t)=16沿求解中带下划线的项回溯，得最短路径解：D(s,t)= 算法设计与分析7问题解决关键n求解过程中起到关键作用的是公式(4.1)，它给出了求该问题最优解的基本性质：原始问题最优解与子问题的最优解存在递归关系，称这种关系为问题的最优子结构。最优子结构。最优子结构为构造求解问题的最优决策序列提供了重要线索，它提示可以自底向上的方式逐次由子问题最优解构造原始问题的最优解。n公式(4.1)还有一个重要特征：由给出的自顶向下的递归分解中，每次产生的子问题求解的关键（例如，求C(v,t)）与原问题是类似的，只是在相对较小的子问题空间中考虑问题的解，因此子问题与原始问题存在相似性相似性。而且这

7、些子问题的解在不同的上一级问题中都需要用到，这种特征可以称为子问题重叠子问题重叠。 算法设计与分析8n采用邻接矩阵表示图G，其中wij为G中边的权，如果不是G的边, 则wij=。G的节点集V=0,1,2,n，其中V0=0是起始点集，Vk=n是终点集，V0,V1,Vk中各子集非空、两两不交。设V1=1，2，.r1，V2= r1+1，r1+2， r2，Vk-1= rk-2+1，rk-2+2，. (n-1)。n【算法3-1】MultiStage_Graph S1: 初始化：j=n-1；对i=0,1,n，ci=0； / ci为节点i到终点n的最短路径长S2: 求节点r，使得wjr+cr=minwji+

8、ci|是G的边; /按照V0,V1,Vk对节点的标记，ji。S3: cj=wjr+cr, Dj=r; / Dj=r 表示边是从j出发到n的最短路径上第1条边 S4: j=j-1;S5: 如果j0则转S2;S6: 输出从源点0出发的最短路径长c0 ；p0=0, pk=n;S7: 对j=1,2,k，pj=Dpj-1; /最短路径Path=算法设计与分析9MultiStage_Graph算法复杂度nG用邻接矩阵表示，对于S2到S5的主循环执行n次。为求满足wjr+cr=minwji+ci|是G的边的r，最多要求n-1次比较。因此时间复杂性为O(n2)。除输入G，输出P外，要求附加存储空间c、D。n如

9、果G采用邻接表表示，求满足最小性的节点r仅对属于G的边访问一次，此算法的时间复杂性应该为O(n+e)（e为G的边数）。n一般地，为避免递归过程中的重复计算，每个子问题首次处理时将结果保存以备查。在上面的过程中，每一次求得的cj都必须记录下来。 算法设计与分析10从源点往后推n算法4-1完全是从汇点往前推，实际上我们也可以用同样的思想，从源点出发往后推。 阶段1: C(s,1)=w(s,1)=4， C(s,2)=w(s,2)=2, C(s,3)=w(s,3)=3阶段2: C(s,4)=minw(1,4)+C(s,1), w(2,4)+C(s,2)=min14,8= 8C(s,5)=minw(1,

10、5)+C(s,1), w(2,5)+C(s,2), w(3,5)+C(s,3) =min13,9,6= 6C(s,6)=minw(2,6)+C(s,2), w(3,6)+C(s,3)=min12,11= 11阶段3: C(s,7)=minw(4,7)+C(s,4), w(5,7)+C(s,5), w(6,7)+C(s,6) =min12,15,16= 12C(s,8)=minw(4,8)+C(s,4), w(5,8)+C(s,5), w(6,8)+C(s,6) =min16,12,15= 12阶段4: C(s,t)=minw(7,t)+C(s,7), w(8,t)+C(s,8)=min20,1

11、6= 16算法设计与分析11MultiStage_Graph2() /*用用Ck来记录到达每一个结点的最短距离来记录到达每一个结点的最短距离, m是划分的段数是划分的段数,Vk表表示到达了哪一段示到达了哪一段 */ C01=0; for (k=1;k=m;k+) for( i=1; i=Vk中结点的数目中结点的数目;i+) /*本循环求第本循环求第K段中所有顶点到段中所有顶点到S的最短路径的最短路径*/ current=MAX; /*对于对于K段中的一个点段中的一个点i，求出，求出K-1段中所有的点到它的距离，记录下段中所有的点到它的距离，记录下从原点出发最短的那一个从原点出发最短的那一个*/

12、 for(j=1;j=Vk-1中结点的数目中结点的数目;j+) r =d(Vki,Vk-1j)+Ck-1j; if (r current) rec=j; current= r ; Cki=current; 将结点将结点Vki指向结点结点指向结点结点Vk-1rec; 从从T到到S沿沿VK逆向输出；逆向输出； 算法设计与分析12图中任意两点间的最短距离n如果上面的图不是分段图，仍然可以用此方法来求图中任意两点间的最短路径，这就是大名鼎鼎的Floyd算法。程序段如下： n for (k=1;k=vtxnum;k+) for (i=1; i=vtxnum;i+) for (j=1; j=vtxnum;

13、j+) if (lengthik+lengthkjlengthij) lengthij=lengthik+lengthkj; pathi,j=pathi,k+pathk,j; 算法设计与分析13矩阵连乘问题n给定n个矩阵：A1, A2, , An，其中Ai与Ai+1是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。n设A和B分别是pq和qr的两个矩阵，则乘积C=AB为pr的矩阵，计算量为pqr次数乘。n但是对于多于2个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很大的差别。算法设计与分析14不同计算顺序的差别n设矩阵A1, A2和A3分别为10100, 1005

14、和550的矩阵，现要计算A1A2A3 。n若按(A1A2)A3)来计算，则需要的数乘次数为101005 + 10550 = 7500n若按(A1(A2 A3)来计算，则需要的数乘次数为100 5 50+ 1010050 = 75000n后一种计算顺序的计算量竟是前者的10倍！n所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要的。算法设计与分析15不同计算顺序的数量n设n个矩阵的连乘积有P(n)个不同的计算顺序。n先在第k个和第k+1个矩阵之间将原矩阵序列分成两个矩阵子序列，k=1,n；再分别对两个子序列完全加括号，最后对结果加括号，便得到原序列的一种完全加括号方式。n由此可得出关于P(n)

15、的递归式：P(n) = n = 1n1P(k) P(nk) n1k=1 n解此递归方程可得P(n) = C(n1)，其中C(n) = 1n+12n n= (4n/n3/2)n所以P(n)随n的增长呈指数增长。因而穷举搜索法不是有效的算法。算法设计与分析16分解最优解的结构n将矩阵连乘积AiAi+1Aj记为Ai: j。n若A1: n 的一个最优解是在矩阵Ak和Ak+1处断开的，即A1: n = (A1: k Ak+1: n)，则A1: k和Ak+1: n也分别是最优解。n事实上，若A1: k的一个计算次序所需计算量更少的话，则用此计算次序替换原来的次序，则得到A1: n一个更少的计算量，这是一个

16、矛盾。同理Ak+1: n也是最优解。n最优子结构性质：最优解的子结构也最优的。最优子结构性质：最优解的子结构也最优的。算法设计与分析17建立递归关系n令mij , 1i, jn，为计算Ai, j 的最少数乘次数，则原问题为m1n。n当i = j时，Ai, j为单一矩阵， mij = 0；n当ij时，利用最优子结构性质有： mij = minmik + mk+1j + pi1pkpjikj其中矩阵Ai (1in)的维数为pi1pi。n根据此递归式就可以直接用递归程序来实现。算法设计与分析18直接递归的时间复杂性n根据前面的递归式不难得出的时间复杂性为 n1(T(k) + T(nk) + 1) k

17、=1 T(n) n1 = (n 1) +(T(k) + T(nk) k=1 n1 n1 = (n-1) +T(k) + T(nk) k=1 k=1 n可用数学归纳法证明T(n)2n1 = (2n)。 n直接递归算法的时间复杂性随n的指数增长。 n1 = n + 2T(k) k=1 算法设计与分析19直接递归中有大量重复计算n直接递归中有大量重复计算，如A1: 4计算中：1: 41: 12: 41: 23: 41: 34: 42: 23: 42: 34: 41:12: 23: 34: 41: 12: 31: 23: 33: 34: 42: 23: 32: 23: 31: 12: 2图中红框标出的

18、都是重复计算。算法设计与分析20消除重复的计算n要消除重复计算，可在计算过程中保存已解决的子问题的答案。这样，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免重复计算。n计算方式可依据递归式自底向上地进行。n注意到在此问题中，不同的有序对 (i, j)就对应不同的子问题，因此不同的子问题个数最多只有Cn2+ n = (n2)个。n这样便可以得到多项式时间的算法。算法设计与分析21自底向上的计算n例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m14其中mii = 0mii+1 = pi1pipi

19、+1mij = minikj mik+mk+1j+pi1pkpj例如： m13 = min m11+m23+p0p1p3m12+m33+p0p2p3算法设计与分析22消除重复的矩阵连乘算法nInt MatrixChain(int *p, int n, int *m, int *s)n for (int i = 1; i = n; i+) mii = 0; n /将对角线元素赋值为零，即单个矩阵计算量为0n for (int r = 2; r = n; r+) /r为连续相乘矩阵的个数n for (int i = 1; i = n r +1; i+) n int j = i + r 1;n(5)

20、 mij = mi+1j + pi1*pi*pj;n /计算Ai, j = Ai: i Ai+1: jn sij = i; /记下断点in(7) for (int k = i + 1; k j; k+) n int t = mik + mk+1j + pi1*pk*pj; n /对ikj, 逐个计算Ai, j = Ai: k Ak+1: jn if (t mij) mij = t; sij = k;n /记下较小的mij及相应的断点k nnreturn(m1n);第(5)步与第(7)步能否合在一起?能。此处分开是为了给mij赋初值。算法设计与分析23MatrixChain的运行举例 设要计算矩

21、阵连乘积A1A2A3A4A5A6，其维数分别为3035, 3515, 155, 510, 1020, 2025, 即p0=30, p1=35, p2=15, p3=5, p4=10, p5=20, p6=25。 MatrixChain用矩阵mij, sij存放子问题Ai: j的最小计算量以及相应的断点。123456 1 2 3 4 5 6mij1234561 2 3 4 5 6sijMatrixChain将如下面红色箭头所示的过程逐个计算子问题Ai: j：执行for (int i = 1; i = n; i+) mii = 0后将对角线元素全部置零，即子问题Aii = 0。000000当r=2

22、，执行第(5)句完成了相邻矩阵Aii+1=pi1*pi*pj 的计算，并在sij中添入了相应的断点。其中的第(7)句因为j = i+1(k=i+1)而被跳过去了，实际并没有执行。1575026257501000500012345当r=3，i=1时，执行第(5)句计算A1:12:3， m13 = m23 + p0*p1*p3 = 2625 +30*35*5 = 787578751执行第(7)句计算A1:23:3， t = m12 + m33 + p0*p2*p3 = 15750+0+35*15*5 = 183757875，所以m13不变，断点仍为1。当r=3，i=2时，执行第(5)句计算A2:2

23、3:4，m24 = m34 + p1*p2*p4 = 750 +35*15*10 = 600060002执行第(7)句计算A2:34:4， t = m23+m44+ p1*p3*p4 = 2625+0+35*5*10 = 43756000，所以m24改为4375，断点改为3。43753当r=3，i=3时，执行第(5)句计算A3:34:5，m35 = m45 + p2*p3*p5 = 1000 +15*5*20 = 250025003执行第(7)句计算A3:45:5， t = m34+m55+ p2*p4*p5 = 750+0+15*10*20 = 37502500，所以m35仍为2500，断点

24、仍为3。当r=3，i=4时，执行第(5)句计算A4:45:6，m46 = m56 + p3*p4*p6 = 5000 +5*10*25 = 625062504执行第(7)句计算A4:56:6， t = m45+m66+ p3*p5*p6 = 1000+0+5*20*25 = 35006250，所以m46改为3500，断点改为5。35005类似的，当r=4、5、6时，可以计算出相应的mij及其相应的断点sij，如下图中所示：937537125353753118753105003151253由m16=15125可知这6个矩阵连乘积的最小运算次数为15125。由s16 = 3可知A1: 6的最优计算

25、次序为A1: 3 A4: 6；由s13=1可知A1: 3的最优计算次序为A1: 1 A2: 3；由s46=5可知A4: 6的最优计算次序为A4: 5 A6: 6；因此最优计算次序为：(A1(A2A3)(A4A5)A6)。算法设计与分析24MatrixChain的时间复杂性n算法MatrixChain的主要计算取决于程序中对r、i和k的三重循环。循环体内的计算量为O(1)，1 r、i、kn，三重循环的总次数为O(n3)。因此该算法时间复杂性的上界为O(n3)，比直接递归算法要有效得多。算法使用空间显然为O(n2)。n这种算法称为动态规划。算法设计与分析25动态规划的基本思想n将原问题分解为若干个

26、子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。n这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。n在算法中用表格来保存已经求解的子问题的解，在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。即可查表取出其解，避免了重复计算。算法设计与分析26动态规划的基本要素n最优子结构：问题的最优解是由其子问题的最优解所构成的。n重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质

27、使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。27动态规划与贪心算法的比较n相同点： 都具有最优子结构性质。n不同点： 贪心算法具有贪心选择性质；动态规划算法具有子问题重叠性，子问题空间小； 动态规划算法通常以自底向上自底向上的方式解各子问题；贪心算法则通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。n可用贪心算法时，动态规划方法可能不适用；n可用动态规划方法时，贪心算法可能不适用。算法设计与分析28动态规划的基本方法n动

28、态规划通常可以按以下几个步骤进行：n(1)找出最优解的性质，并刻画其结构特征；n(2)递归地定义最优值；n(3)以自底向上的方式计算出各子结构的最优值并添入表格中保存；n(4)根据计算最优值时得到的信息，构造最优解。n步骤13是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第为此还需要在第3步中记录构造最优解所必需的信息步中记录构造最优解所必需的信息。算法设计与分析29凸多边形最优三角剖分n凸多边形的三角剖分是将一个凸多边形分割成互不相交的三角形的弦的集合T。n下面是一个凸7边形的2个不同的三角剖分：v0v1v2v3v4v5v6v0v1v2v3v4v5v6n在凸多边形的一

29、个三角剖分T中，各弦互不相交，且T已达到最大，即任何一条不在T中的弦必与T中某弦相交。n在有n个顶点的凸多边形的三角剖分中，恰有n3条弦和n2个三角形。n凸多边形的最优三角剖分问题：给定凸多边形P=v0, v1, vn1 ，以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的一个三角剖分，使得该剖分中诸三角形上权之和为最小。n可定义三角形上各种各样的权函数w。n例如w(vivjvk) = |vivj| + |vjvk| + |vkvi|，其中|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。算法设计与分析30三角剖分与矩阵连乘积同构n

30、三角剖分问题和矩阵连乘积问题都对应于一个完全二叉树，也称为表达式的语法树。0123A1A44A2A3A5A6(A1(A2A3)(A4(A5A6)所对应的二叉树v1v0v2v3v4v5v6012A13A2A3A44A5A6凸多边形v0v1v2v3v4v5v6一个三角剖分所对应的二叉树nn个矩阵连乘积计算顺序同构于n个叶子的完全二叉树，凸(n+1)边形三角剖分同构于n个叶子的完全二叉树，所以n个矩阵连乘积的计算顺序问题同构于凸(n+1)边形的三角剖分问题。n事实上，矩阵连乘积最优计算顺序问题相当于是凸多边形最优三角剖分问题中一种特殊定义的权函数的情形。算法设计与分析31最优子结构性质n能应用动态规

31、划求解的问题应具有最优子结构性质。凸多边形最优三角剖分问题具有最优子结构性质。n事实上，若凸(n+1)边形P=v0, v1, vn的一个最优三角剖分T包含了三角形v0vkvn，1kn，则T的权为三角形v0vkvn、多边形v0, v1, vk 和多边形vk, vk+1, vn的权之和。显然这两个子多边形的三角剖分也是最优的。n因为，其中若有一个子多边形的三角剖分不是最优的将导致T不是最优三角剖分的矛盾。算法设计与分析32最优三角剖分的递归结构n定义tij, 1ijn, 为子多边形vi1, vi, vj的最优三角剖分所对应的权函数值，并为方便起见，设退化的多边形vi1, vi的权值为0。n于是凸(

32、n+1)边形的最优三角剖分为t1nn易知，tij可递归定义为n当i = j时，为退化多边形vi1, vi，tij = 0；n当ij时，利用最优子结构性质有： tij = mintik + tk+1j + w(vi1vkvj)ikj与矩阵连乘积问题相对比： mij = minmik + mk+1j + pi1pkpjikjn显然，矩阵连乘积的最优计算顺序与凸多边形最优三角剖分具有完全相同的递归结构。算法设计与分析33最优三角剖分的算法n由于凸多边形最优三角剖分与矩阵连乘积的最优计算顺序具有完全相同的递归结构，其区别仅在于权函数的不同，所以只需要修改求矩阵连乘积的最优计算顺序的算法中的权函数计算便

33、可得到凸多边形最优三角剖分的算法。n显然该算法的时间复杂性也是O(n3)。nVoid MinWeightTriangulation(int n, Type *t, int *s)n for (int i = 1; i = n; i+) tii = 0; n for (int r = 2; r = n; r+) n for (int i = 1; i = n r +1; i+) n int j = i + r 1;n tij = ti+1j + w(i1, i, j);n sij = i; n for (int k = i + 1; k j; k+) n int u = tik + tk+1j

34、+ w(i1, k, j); n if (u tij) tij = u; sij = k;n /程序中红色的部分为改动的地方算法设计与分析34最长公共子序列n给定序列A=，B=。如果存在A的子序列A1=(i1i2ir)和B的子序列B1=(j1j2jr)，使得aik=bjk(k=1,2,.r)，则称C=A1=B1为序列A、B的一个公共子序列。nA,B的长度最大公共子序列称为A,B的最长公共子序列。n例如：A=，B=，C1=是A、B的一个公共子序列，但不是最长子序列。C2=和C3=都是A、B的最长子序列。n注意：这里的子序列对于原序列而言不一定是连续的。 算法设计与分析35求最长公共子序列n对A=

35、，B= 求序列A、B的最长公共子序列的最直接方法是对A的所有子序列逐个检查是否为B的子序列，并且在检查过程中记录最长子序列。nA的每个子序列对应下标集1,2,.n的一个子集，因此遍历所有A的不同子序列要求的时间复杂性为O(2n)。n显然这不是一个有效的方法。算法设计与分析36最长公共子序列性质n对长度为n的序列S=，记Sr= (r=n，Sn=S)。n如果C=是A、B的一个最长公共子序列，则C必为如下三种情况之一：1） 如果an=bm，则cr= an=bm ，即Cr-1是An-1和Bm-1的最长公共子序列；2） 如果anbm且cr an，则C是An-1和B的最长公共子序列；3） 如果anbm且c

36、r bm，则C是A和Bm-1的最长公共子序列；n即两个序列的最长公共子序列包含了这两个序列前缀的最长公共子序列。 算法设计与分析37最长公共子序列的递归结构n以LCS(A,B)表示序列A、B的最长公共子序列，求LCS(A,B)的递归结构如下： 其他或者cba0j0i)B,LCS(A),B,maxLCS(Ac)B,A(LCS)B,A(LCSji1 - jij1i1j1ijin表示空，|表示在子序列尾部添加一个元素。n计算A、B的最长公共子序列可能要求计算A、Bm-1的公共最长子序列或者An-1、B的公共最长子序列，而这两个子问题又都包含求An-1、Bm-1的公共最长子序列。n以len(i,j)表

37、示LCS(Ai,Bj)的长度有： 算法设计与分析38求最长公共子串长度的算法int LCSlength(char *a,char *b,int *len,int *flag)/a、b是输入字符串，输出数组是输入字符串，输出数组len的元素的元素lenij记录记录len(i,j)，/数组数组flag在求在求a、b的最长公共子序列时作为标志使用。的最长公共子序列时作为标志使用。/flagij=0：表示：表示LCS(ai,bj)= LCS(ai-1,bj-1)|ai，ai=bj;/ flagij=1：表示：表示LCS(ai,bj)= LCS(ai-1,bj);/ flagij=-1:表示表示LCS(

38、ai,bj)= LCS(ai,bj-1);n=strlen(a); m=strlen(b);for(i=1;i=n;i+) leni0=0; for(i=1;i=m;i+) len0i=0;for(i=1;i=n;i+) for(j=1;j=lenij-1) lenij=leni-1j; flagij=1; else lenij=lenij-1; flagij=-1; return(lennm);算法设计与分析39求最长公共子串的算法n根据根据LCSlength()输出的标志数组输出的标志数组flag和最长公共子串的和最长公共子串的长度值长度值lennm，按照公式可以得到子字符串，按照公式可以

39、得到子字符串ai、bj的最的最长公共子串长公共子串c：n求求c=LCS(ai,bj) void LCS0(int i,int j,char *a,int k,int *flag,chr *c)/k是当前最长公共子串长度，数组是当前最长公共子串长度，数组flag由由LCSlength()得到得到if (i= =0)|(j= =0) return; if (flagij= =0) LCS0(i-1,j-1,a,k-1,flag,c); ck-1=ai; else if (flagij= =1) LCS0(i-1,j,a,k,flag,c); else LCS0(i,j-1,a,k,flag,c);

40、算法设计与分析40LCS算法运行举例设A=d,b,a,d,b，B=b,a,b,d LCS用矩阵lenij,flagij存放子问题Ai与Bj 的最长公共子串长度和相应的标志012345 0 1 2 3 4 12345 1 2 3 4 lenijflagijLCSlength将如下面红色箭头所示的过程逐个计算子问题执行for(i=0;i=m;i+) leni0=0; for(i=0;i=m;i+) len0i=0;后完成初始化如下：0000000000当i=1，依次比较A1与Bj及len0j与len1j-1，填入len1j与flag1j的值如下： A1B1且len01=len10， len11=l

41、en01=0; flag11=1;01 A1B2且len02=len11， len12=len02=0; flag12=1;010 A1B3且len03=len12， len13=len03=0; flag13=1;1 A1=B4 ， len14=len03+1=1; flag14=0;10当i=2，依次比较A2与Bj及len1j与len2j-1，填入len2j与flag2j的值如下： A2=B1 ， len21=len10+1=1; flag21=0;10 A2B2 且len12len21; len22=len21=1; flag22= -1;1-1 A2=B3; len23=len12+1

42、=1; flag23= 0;10 A2B4且len14bk时，k=k+1,bk=ai当aibk时，k不变，更新b1:k若aib1,则b1=ai;否则找到j,满足bj-1aibj，修改bj=ai;n用bi记录以ai,0in为结尾元素的最长递增子序列的长度，则序列a的递增最长子序列的长度为 。n递归定义bi为： 算法设计与分析47max0ibni100max0kbibbiakaik作业：n3-1 设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。n3-5 给定n种物品和一背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物

43、品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。算法设计与分析48算法设计与分析49多边形游戏(自学)n有一个n边形，每个顶点被赋予一整数值，每条边上被赋予一个运算符“+”或“-”。n游戏的第1步，将一条边删去；n随后的n1步按以下方式操作：n(1)选择一条边e及其所连接的两个顶点v1和v2；n(2) 用一个新顶点取代边e以及顶点v1和v2，赋予新顶点的值为顶点v1和v2的值通过边e上的运算所得到的值。n最后所有的边被删去，所剩顶点的值即为得分算法设计与分析50多边形游戏的表达n设所有的边依次从1到n编号，按顺时针序列为op1, v1, op2, v2, , opn, vn 其中opi为边i上的运算符，vi为顶点i上的值。n将多边形中始于顶点i (1in)，长度为j 的顺时针链vi, opi+1, , vi+j1表示为p(i, j)。n若链p(i, j)最后一次合并在opi+s(1sj1)处发生，则被分割为两个子链p(i, s)和p(i+s, js