第四章动态规划法课件

算法设计与分析1第四章

动态规划算法设计与分析2问题的分解将待求解问题分解为若干子问题，通过子问题的解得到原问题的解，这是问题求解的有效途径。但是如何实施分解？分治策略的基本思想是将规模为n的问题分解为k个规模较小的子问题，各子问题相互独立但与原问题求解策略相同。并不是所有问题都可以这样处理。问题分解的另一个途径是将求解过程分解为若干阶段（级），依次求解每个阶段即得到原问题的解。通过分解得到的各子阶段不要求相互独立，但希望它们具有相同类型，而且前一阶段的输出可以作为下一阶段的输入。这种策略特别适合求解具有某种最优性质的问题。贪心法属于这类求解策略：对问题P(n)，其求解过程中各贪心选择步骤构成决策序列D=<D1,D2,..Dk>。Di的最优性仅依赖于D1,D2,..Di-1。贪心法不保证决策序列D最后求出解的最优性。算法设计与分析3动态规划动态规划也是一个分阶段判定决策过程，其问题求解策略的基础是决策过程的最优原理：为达到某问题的最优目标T，需要依次作出决策序列D=<D1,…Dk>。如果D是最优的，则对任意i(1≤i<k)，决策子序列Di+1,…Dk也是最优的，即当前决策的最优性取决于其后续决策序列的是否最优。由此追溯至目标，再由最终目标决策向上回溯，导出决策序列D=<D1,…Dk>，因此动态规划方法可以保证问题求解是全局最优的。也可以这样理解：如果求最优解的问题可以划分成若干段（级），那么最后求得的最优解是由各个部分解所组成，而这些部分解一定是对应阶段的最优解。算法设计与分析4最短路径给定简单有向连通赋权图G=<V,E,w>，w(i,j)是G中边<i,j>的权。顶点集V可以划分为k+1个两两不交的子集Vi，i=0,1,2,..k。其中V0={s}，Vk={t}。对G中任一边<u,v>，存在Vi、Vi+1，使得u属于Vi，v属于Vi+1，其中0≤i<k。称G为k段图，s点为起点，t为终点。在G中求s出发到t的最短路径。这里"最短"是指s到t的路径上各边权的和最小。算法设计与分析5一个多段图例子

记D(u,v)是G中起点为u,终点为v的最短路径，C(u,v)是该路径上各边权的和。设D(s,t)=<s,vi1,vi2…vik-1,t>，vir属于Vr（r=1,2..k-1），则D(vi1,t)=<vi1,vi2,…vik-1,t>是从vi1出发到t的最短路径，D(vi2,t)=<vi2,…vik-1,t>是从vi2出发到t的最短路径等等。设u属于Vi，有：C(u,t)=min{w(u,v)+C(v,t)} (4.1)

v∈Vi+1

阶段4:C(7,t)=w(7,t)=8，C(8,t)=w(8,t)=4阶段3:C(4,t)=min{w(4,7)+C(7,t),w(4,8)+C(8,t)}=12

C(5,t)=min{w(5,7)+C(7,t),w(5,8)+C(8,t)}=10

C(6,t)=min{w(6,7)+C(7,t),w(6,8)+C(8,t)}=8阶段2:C(1,t)=min{w(1,4)+C(4,t),w(1,5)+C(5,t)}=19

C(2,t)=min{w(2,4)+C(4,t),w(2,5)+C(5,t),w(2,6)+C(6,t)}=17

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

算法设计与分析7采用邻接矩阵表示图G，其中wij为G中边<i,j>的权，如果<i,j>不是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)}。【算法4-1】MultiStage_Graph

S1:初始化：j=n-1；对i=0,1,…n，ci=0；//ci为节点i到终点n的最短路径长

S2:求节点r，使得wjr+cr=min{wji+ci|<j,i>是G的边};//按照{V0,V1,…Vk}对节点的标记，j<i。

S3:cj=wjr+cr,Dj=r;//Dj=r表示边<j,r>是从j出发到n的最短路径上第1条边

S4:j=j-1;

S5:如果j≥0则转S2;

S6:输出从源点0出发的最短路径长c0

；p0=0,pk=n;

S7:对j=1,2,…k，pj=Dpj-1;//最短路径Path=<p0,p1,…pk>算法设计与分析8MultiStage_Graph算法复杂度G用邻接矩阵表示，对于S2到S5的主循环执行n次。为求满足wjr+cr=min{wji+ci|<j,i>是G的边}的r，最多要求n-1次比较。因此时间复杂性为O(n2)。除输入G，输出P外，要求附加存储空间c、D。如果G采用邻接表表示，求满足最小性的节点r仅对属于G的边<j,r>访问一次，此算法的时间复杂性应该为O(n+e)（e为G的边数）。一般地，为避免递归过程中的重复计算，每个子问题首次处理时将结果保存以备查。在上面的过程中，每一次求得的cj都必须记录下来。算法设计与分析9从源点往后推算法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)=min{w(1,4)+C(s,1),w(2,4)+C(s,2)}=min{14,8}=8C(s,5)=min{w(1,5)+C(s,1),w(2,5)+C(s,2),w(3,5)+C(s,3)} =min{13,9,6}=6C(s,6)=min{w(2,6)+C(s,2),w(3,6)+C(s,3)}=min{12,11}=11阶段3:C(s,7)=min{w(4,7)+C(s,4),w(5,7)+C(s,5),w(6,7)+C(s,6)} =min{12,15,16}=12C(s,8)=min{w(4,8)+C(s,4),w(5,8)+C(s,5),w(6,8)+C(s,6)} =min{16,12,15}=12阶段4:C(s,t)=min{w(7,t)+C(s,7),w(8,t)+C(s,8)}=min{20,16}=16算法设计与分析10MultiStage_Graph2()

{/*用Ck来记录到达每一个结点的最短距离,m是划分的段数,Vk表示到达了哪一段*/

C0[1]=0;

for(k=1;k<=m;k++)

{for(i=1;i<=Vk中结点的数目;i++)/*本循环求第K段中所有顶点到S的最短路径*/

{current=MAX;

/*对于K段中的一个点i，求出K-1段中所有的点到它的距离，记录下从原点出发最短的那一个*/

for(j=1;j<=Vk-1中结点的数目;j++)

{r=d(Vk[i],Vk-1[j])+Ck-1[j];

if(r<current)

{rec=j;

current=r;}

}

Ck[i]=current;

将结点Vk[i]指向结点结点Vk-1[rec];

}

}

从T到S沿VK逆向输出；

}算法设计与分析11图中任意两点间的最短距离如果上面的图不是分段图，仍然可以用此方法来求图中任意两点间的最短路径，这就是大名鼎鼎的Floyd算法。程序段如下：

for(k=1;k<=vtxnum;k++)

for(i=1;i<=vtxnum;i++)

for(j=1;j<=vtxnum;j++)

if(length[i][k]+length[k][j]<length[i][j])

{length[i][j]=length[i][k]+length[k][j];

path[i,j]=path[i,k]+path[k,j];}算法设计与分析12矩阵连乘问题给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。设A和B分别是p×q和q×r的两个矩阵，则乘积C=AB为p×r的矩阵，计算量为pqr次数乘。但是对于多于2个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很大的差别。算法设计与分析13不同计算顺序的差别设矩阵A1,A2和A3分别为10×100,100×5和5×50的矩阵，现要计算A1A2A3。若按((A1A2)A3)来计算，则需要的数乘次数为10×100×5+10×5×50=7500若按(A1(A2A3))来计算，则需要的数乘次数为100×5×50+10×100×50=75000后一种计算顺序的计算量竟是前者的10倍！所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要的。算法设计与分析14不同计算顺序的数量设n个矩阵的连乘积有P(n)个不同的计算顺序。先在第k个和第k+1个矩阵之间将原矩阵序列分成两个矩阵子序列，k=1,…,n；再分别对两个子序列完全加括号，最后对结果加括号，便得到原序列的一种完全加括号方式。由此可得出关于P(n)的递归式：P(n)=n=1n–1∑P(k)P(n–k)n＞1k=1

解此递归方程可得P(n)=C(n–1)，其中C(n)=

1n+12nn=Ω(4n/n3/2)所以P(n)随n的增长呈指数增长。因而穷举搜索法不是有效的算法。算法设计与分析15分解最优解的结构将矩阵连乘积AiAi+1…Aj记为A[i:j]。若A[1:n]的一个最优解是在矩阵Ak和Ak+1处断开的，即A[1:n]=(A[1:k]A[k+1:n])，则A[1:k]和A[k+1:n]也分别是最优解。事实上，若A[1:k]的一个计算次序所需计算量更少的话，则用此计算次序替换原来的次序，则得到A[1:n]一个更少的计算量，这是一个矛盾。同理A[k+1:n]也是最优解。最优子结构性质：最优解的子结构也最优的。算法设计与分析16建立递归关系令m[i][j],1≤i,j≤n，为计算A[i,j]的最少数乘次数，则原问题为m[1][n]。当i=j时，A[i,j]为单一矩阵，m[i][j]=0；当i＜j时，利用最优子结构性质有：m[i][j]=min{m[i][k]+m[k+1][j]+pi–1pkpj}i≤k＜j其中矩阵Ai(1≤i≤n)的维数为pi–1×pi。根据此递归式就可以直接用递归程序来实现。算法设计与分析17直接递归的时间复杂性根据前面的递归式不难得出的时间复杂性为n–1∑(T(k)+T(n–k)+1)k=1

T(n)≥n–1=(n–1)+∑(T(k)+T(n–k))k=1

n–1n–1=(n-1)+∑T(k)+∑T(n–k)k=1k=1

可用数学归纳法证明T(n)≥2n–1=Ω(2n)。直接递归算法的时间复杂性随n的指数增长。

n–1=n+2∑T(k)k=1

算法设计与分析18直接递归中有大量重复计算直接递归中有大量重复计算，如A[1: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图中红框标出的都是重复计算。算法设计与分析19消除重复的计算要消除重复计算，可在计算过程中保存已解决的子问题的答案。这样，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免重复计算。计算方式可依据递归式自底向上地进行。注意到在此问题中，不同的有序对(i,j)就对应不同的子问题，因此不同的子问题个数最多只有Cn2+n=Θ(n2)个。这样便可以得到多项式时间的算法。算法设计与分析20自底向上的计算例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m[1][1]m[2][2]m[3][3]m[4][4]m[1][2]m[2][3]m[3][4]m[1][3]m[2][4]m[1][4]其中m[i][i]=0m[i][i+1]=pi–1pipi+1m[i][j]=mini≤k＜j

{m[i][k]+m[k+1][j]+pi–1pkpj}例如：m[1][3]=minm[1][1]+m[2][3]+p0p1p3m[1][2]+m[3][3]+p0p2p3算法设计与分析21消除重复的矩阵连乘算法IntMatrixChain(intp,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;

//将对角线元素赋值为零，即单个矩阵计算量为0for(intr=2;r<=n;r++)//r为连续相乘矩阵的个数

for(inti=1;i<=n–r+1;i++){intj=i+r–1;(5)m[i][j]=m[i+1][j]+p[i–1]*p[i]*p[j];

//计算A[i,j]=A[i:i]A[i+1:j]s[i][j]=i;//记下断点i(7)for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i–1]*p[k]*p[j];

//对i<k<j,逐个计算A[i,j]=A[i:k]A[k+1:j]if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}

//记下较小的m[i][j]及相应的断点k

}}return(m[1][n]);}第(5)步与第(7)步能否合在一起?能。此处分开是为了给m[i][j]赋初值。算法设计与分析22MatrixChain的运行举例

设要计算矩阵连乘积A1A2A3A4A5A6，其维数分别为35×35,35×15,15×5,5×10,10×20,20×25,即p0=35,p1=35,p2=15,p3=5,p4=10,p5=20,p6=25。MatrixChain用矩阵m[i][j],s[i][j]存放子问题A[i:j]的最小计算量以及相应的断点。123456

123456m[i][j]123456123456s[i][j]MatrixChain将如下面红色箭头所示的过程逐个计算子问题A[i:j]：执行for(inti=1;i<=n;i++)m[i][i]=0后将对角线元素全部置零，即子问题A[i][i]=0。000000当r=2，执行第(5)句完成了相邻矩阵A[i][i+1]=p[i–1]*p[i]*p[j]的计算，并在s[i][j]中添入了相应的断点。其中的第(7)句因为j=i+1(k=i+1)而被跳过去了，实际并没有执行。1575026257501000500012345当r=3，i=1时，执行第(5)句计算A[1:1][2:3]，m[1][3]=m[2][3]+p[0]*p[1]*p[3]=2625+30*35*5=787578751执行第(7)句计算A[1:2][3:3]，t=m[1][2]+m[3][3]+p[0]*p[2]*p[3]=15750+0+35*15*5=18375＞7875，所以m[1][3]不变，断点仍为1。当r=3，i=2时，执行第(5)句计算A[2:2][3:4]，m[2][4]=m[3][4]+p[1]*p[2]*p[4]=750+35*15*10=600060002执行第(7)句计算A[2:3][4:4]，t=m[2][3]+m[4][4]+p[1]*p[3]*p[4]=2625+0+35*5*10=4375＜6000，所以m[2][4]改为4375，断点改为3。43753当r=3，i=3时，执行第(5)句计算A[3:3][4:5]，m[3][5]=m[4][5]+p[2]*p[3]*p[5]=1000+15*5*20=250025003执行第(7)句计算A[3:4][5:5]，t=m[3][4]+m[5][5]+p[2]*p[4]*p[5]=750+0+15*10*20=3750＞2500，所以m[3][5]仍为2500，断点仍为3。当r=3，i=4时，执行第(5)句计算A[4:4][5:6]，m[4][6]=m[5][6]+p[3]*p[4]*p[6]=5000+5*10*25=625062504执行第(7)句计算A[4:5][6:6]，t=m[4][5]+m[6][6]+p[3]*p[5]*p[6]=1000+0+5*20*25=3500＜6250，所以m[4][6]改为3500，断点改为5。35005类似的，当r=4、5、6时，可以计算出相应的m[i][j]及其相应的断点s[i][j]，如下图中所示：937537125353753118753105003151253由m[1][6]=15125可知这6个矩阵连乘积的最小运算次数为15125。由s[1][6]=3可知A[1:6]的最优计算次序为A[1:3]A[4:6]；由s[1][3]=1可知A[1:3]的最优计算次序为A[1:1]A[2:3]；由s[4][6]=5可知A[4:6]的最优计算次序为A[4:5]A[6:6]；因此最优计算次序为：(A1(A2A3))((A4A5)A6)。算法设计与分析23MatrixChain的时间复杂性算法MatrixChain的主要计算取决于程序中对r、i和k的三重循环。循环体内的计算量为O(1)，1≤r、i、k≤n，三重循环的总次数为O(n3)。因此该算法时间复杂性的上界为O(n3)，比直接递归算法要有效得多。算法使用空间显然为O(n2)。这种算法称为动态规划。算法设计与分析24动态规划的基本思想将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。算法设计与分析25动态规划的基本要素最优子结构：问题的最优解是由其子问题的最优解所构成的。重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。算法设计与分析26动态规划的基本方法动态规划通常可以按以下几个步骤进行：(1)找出最优解的性质，并刻画其结构特征；(2)递归地定义最优值；(3)以自底向上的方式计算出各子结构的最优值并添入表格中保存；(4)根据计算最优值时得到的信息，构造最优解。步骤1~3是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。算法设计与分析27最长公共子序列给定序列A=<a1,a2,…,ak,...,an>，B=<b1,b2,…,bk,...,bm>。如果存在A的子序列A1=<ai1,ai2,…,air>(i1<i2<…<ir)和B的子序列B1=<bj1,bj2,…,bjr>(j1<j2<…<jr)，使得aik=bjk(k=1,2,..r)，则称C=A1=B1为序列A、B的一个公共子序列。A,B的长度最大公共子序列称为A,B的最长公共子序列。例如：A=<a,b,c,b,d,a,c,b>，B=<b,d,c,a,b>，C1=<b,a,b>是A、B的一个公共子序列，但不是最长子序列。C2=<b,d,a,b>和C3=<b,c,a,b>都是A、B的最长子序列。注意：这里的子序列对于原序列而言不一定是连续的。算法设计与分析28求最长公共子序列对A=<a1,a2,…,ak,...,an>，B=<b1,b2,…,bk,...,bm>求序列A、B的最长公共子序列的最直接方法是对A的所有子序列逐个检查是否为B的子序列，并且在检查过程中记录最长子序列。A的每个子序列对应下标集{1,2,...n}的一个子集，因此遍历所有A的不同子序列要求的时间复杂性为O(2n)。显然这不是一个有效的方法。

算法设计与分析29最长公共子序列性质对长度为n的序列S=<s1,s2,…,sk,...,sn>，记Sr=<s1,s2,…,sr>(r<=n，Sn=S)。如果C=<c1,c2,…,cr>是A、B的一个最长公共子序列，则C必为如下三种情况之一：

1）如果an=bm，则cr=an=bm

，即Cr-1是An-1和Bm-1的最长公共子序列；

2）如果an≠bm且cr≠an，则C是An-1和B的最长公共子序列；

3）如果an≠bm且cr≠bm，则C是A和Bm-1的最长公共子序列；即两个序列的最长公共子序列包含了这两个序列前缀的最长公共子序列。算法设计与分析30最长公共子序列的递归结构以LCS(A,B)表示序列A、B的最长公共子序列，求LCS(A,B)的递归结构如下：Φ表示空，||表示在子序列尾部添加一个元素。计算A、B的最长公共子序列可能要求计算A、Bm-1的公共最长子序列或者An-1、B的公共最长子序列，而这两个子问题又都包含求An-1、Bm-1的公共最长子序列。以len(i,j)表示LCS(Ai,Bj)的长度有：算法设计与分析31求最长公共子串长度的算法intLCSlength(char*a,char*b,int**len,int**flag)//a、b是输入字符串，输出数组len的元素len[i][j]记录len(i,j)，//数组flag在求a、b的最长公共子序列时作为标志使用。//flag[i][j]=0：表示LCS(ai,bj)=LCS(ai-1,bj-1)||{a[i]}，a[i]=b[j];//flag[i][j]=1：表示LCS(ai,bj)=LCS(ai-1,bj);//flag[i][j]=-1:表示LCS(ai,bj)=LCS(ai,bj-1);{m=strlen(a);n=strlen(b);for(i=0;i<=m;i++)

len[i][0]=0;

for(i=1;i<=n;i++)

len[0][i]=0;for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if(a[i]==b[j])

{len[i][j]=len[i-1][j-1]+1;

flag[i][j]=0;}

elseif(len[i-1][j]>=len[i][j-1])

{len[i][j]=len[i-1][j];

flag[i][j]=1;

}

else

{len[i][j]=len[i][j-1];

flag[i][j]=-1;

}

return(len[m][n]);}算法设计与分析32求最长公共子串的算法根据LCSlength()输出的标志数组flag和最长公共子串的长度值len[m][n]，按照公式可以得到子字符串ai、bj的最长公共子串c：求c=LCS(ai,bj)

voidLCS0(inti,intj,char*a,intk,int**flag,chr*c)//k是当前最长公共子串长度，数组flag由LCSlength()得到{if((i==0)||(j==0))

return;

if(flag[i][j]==0){LCS0(i-1,j-1,a,k-1,flag,c);

c[k-1]=a[i];}

elseif(flag[i][j]==1)LCS0(i-1,j,a,k,flag,c);else

LCS0(i,j-1,a,k,flag,c);

}算法设计与分析33LCS算法运行举例设A={d,b,a,d,b}，B={b,a,b,d} LCS用矩阵len[i][j],flag[i][j]存放子问题Ai与Bj

的最长公共子串长度和相应的标志012345

0

1234123451234len[i][j]flag[i][j] LCSlength将如下面红色箭头所示的过程逐个计算子问题

执行for(i=0;i<=m;i++)len[i][0]=0;for(i=0;i<=m;i++)len[0][i]=0;

后完成初始化如下：0000000000

当i=1，依次比较A[1]与B[j]及len[0][j]与len[1][j-1]，填入len[1][j]与flag[1][j]的值如下：∵

A[1]<>B[1]且len[0][1]=len[1][0]，∴len[1][1]=len[0][1]=0;flag[1][1]=1;01∵

A[1]<>B[2]且len[0][2]=len[1][1]，∴len[1][2]=len[0][2]=0;flag[1][2]=1;010∵

A[1]<>B[3]且len[0][3]=len[1][2]，∴len[1][3]=len[0][3]=0;flag[1][3]=1;1∵

A[1]=B[4]，∴len[1][4]=len[0][3]+1=1;flag[1][4]=0;10

当i=2，依次比较A[2]与B[j]及len[1][j]与len[2][j-1]，填入len[2][j]与flag[2][j]的值如下：∵

A[2]=B[1]，∴len[2][1]=len[1][0]+1=1;flag[2][1]=0;10∵

A[2]<>B[2]且len[1][2]<len[2][1];∴len[2][2]=len[2][1]=1;flag[2][2]=-1;1-1∵

A[2]=B[3];∴len[2][3]=len[1][2]+1=1;flag[2][3]=0;10∵

A[2]<>B[4]且len[1][4]<len[2][3];∴len[2][4]=len[2][3]=2;flag[2][4]=-1;11

类似的，当i=3，4，5时可以计算出相应的len[i][j]及flag[i][j]，如下图所示：12102-12-1112-1213010213031

故得到最长公共子串C长度为k=3；最后再由flag标识根据算法LCS0得到C={b,a,d}。算法设计与分析34LCS的时间复杂性算法LCSlength的主要计算取决于程序中对i和j的二重循环，循环的总次数为O(nm)。算法LCS0的每次递归调用中i减1或者j减1，因此时间复杂性为O(n+m)，。算法设计与分析35凸多边形最优三角剖分凸多边形的三角剖分是将一个凸多边形分割成互不相交的三角形的弦的集合T。下面是一个凸7边形的2个不同的三角剖分：v0v1v2v3v4v5v6v0v1v2v3v4v5v6在凸多边形的一个三角剖分T中，各弦互不相交，且T已达到最大，即任何一条不在T中的弦必与T中某弦相交。在有n个顶点的凸多边形的三角剖分中，恰有n–3条弦和n–2个三角形。凸多边形的最优三角剖分问题：给定凸多边形P={v0,v1,…,vn–1}，以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的一个三角剖分，使得该剖分中诸三角形上权之和为最小。可定义三角形上各种各样的权函数w。例如w(vivjvk)=|vivj|+|vjvk|+|vkvi|，其中|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。算法设计与分析36三角剖分与矩阵连乘积同构三角剖分问题和矩阵连乘积问题都对应于一个完全二叉树，也称为表达式的语法树。0123A1A44A2A3A5A6((A1(A2A3))(A4(A5A6))所对应的二叉树v1v0v2v3v4v5v6012A13A2A3A44A5A6凸多边形v0v1v2v3v4v5v6一个三角剖分所对应的二叉树n个矩阵连乘积计算顺序同构于n个叶子的完全二叉树，凸(n+1)边形三角剖分同构于n个叶子的完全二叉树，所以n个矩阵连乘积的计算顺序问题同构于凸(n+1)边形的三角剖分问题。事实上，矩阵连乘积最优计算顺序问题相当于是凸多边形最优三角剖分问题中一种特殊定义的权函数的情形。算法设计与分析37最优子结构性质能应用动态规划求解的问题应具有最优子结构性质。凸多边形最优三角剖分问题具有最优子结构性质。事实上，若凸(n+1)边形P={v0,v1,…,vn}的一个最优三角剖分T包含了三角形v0vkvn，1≤k＜n，则T的权为三角形v0vkvn、多边形{v0,v1,…,vk}和多边形{vk,vk+1,…,vn}的权之和。显然这两个子多边形的三角剖分也是最优的。因为，其中若有一个子多边形的三角剖分不是最优的将导致T不是最优三角剖分的矛盾。算法设计与分析38最优三角剖分的递归结构定义t[i][j],1≤i<j≤n,为子多边形{vi–1,vi,…,vj}的最优三角剖分所对应的权函数值，并为方便起见，设退化的多边形{vi–1,vi}的权值为0。于是凸(n+1)边形的最优三角剖分为t[1][n]易知，t[i][j]可递归定义为当i=j时，为退化多边形{vi–1,vi}，t[i][j]=0；当i＜j时，利用最优子结构性质有：t[i][j]=min{t[i][k]+t[k+1][j]+w(vi–1vkvj)}i≤k＜j与矩阵连乘积问题相对比：m[i][j]=min{m[i][k]+m[k+1][j]+pi–1pkpj}i≤k＜j显然，矩阵连乘积的最优计算顺序与凸多边形最优三角剖分具有完全相同的递归结构。算法设计与分析39最优三角剖分的算法由于凸多边形最优三角剖分与矩阵连乘积的最优计算顺序具有完全相同的递归结构，其区别仅在于权函数的不同，所以只需要修改求矩阵连乘积的最优计算顺序的算法中的权函数计算便可得到凸多边形最优三角剖分的算法。显然该算法的时间复杂性也是O(n3)。VoidMinWeightTriangulation(intn,Type**t,int**s){for(inti=1;i<=n;i++)t[i][i]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n–r+1;i++){intj=i+r–1;t[i][j]=

t[i+1][j]+w(i–1,i,j);s[i][j]=i;for(intk=i+1;k<j;k++){intu=t[i][k]+t[k+1][j]+w(i–1,k,j);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}}//程序中红色的部分为改动的地方算法设计与分析40动态规划总结与分治法相比，相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有重叠。基本思想是造表记录已解的子问题，再次遇到时仅查表即可，避免了重复计算，提高效率。通常用于求解具有最优性质的问题，而且其子问题也具有最优性质(最优子结构性质)。实现方法通常为自底向上的递归形式，但也可以采用自上而下的形式(备忘录方法)。算法设计与分析41课堂练习最大子段和问题给定由n个整数（可能有负整数）组成的序列，a1,a2,……,an,求该序列中连续子段和的最大值。当所有整数均为负数时，定义其最大子段和为0。例如：序列（-2,11,-4,13,-5,-1），最大子段和为：(11,-4,13)=20。S(ai)表示以ai为最末字符的连续子串的最大值令S(a0)=0则S(ai)=max{S(ai-1)+ai,ai|i=1,2,....,n}算法设计与分析42算法设计与分析43课堂练习递增最长子序列问题已知序列A=（a1,a2,....,an），设计一个动态规划算法，能在O(n2)的时间内求出该序列的递增最长子序列。例如：序列A=（5,

12,

46,32,1,45,7,9,51,10,18

）

它的递增最长子序列为：（1,7,9,10,18

）或者（

5,7,9,10,18）（只要找到一个即可）算法设计与分析44用b[j]记序列a[1:j]中最长单调递增子序列的长度，s[j]为序列a[1:j]中所有长度为b[j]的单调递增子序列末尾元素的最小值。则算法设计与分析45多边形游戏有一个n边形，每个顶点被赋予一整数值，每条边上被赋予一个运算符“+”或“-”。游戏的第1步，将一条边删去；随后的n–1步按以下方式操作：(1)选择一条边e及其所连接的两个顶点v1和v2；(2)

用一个新顶点取代边e以及顶点v1和v2，赋予新顶点的值为顶点v1和v2的值通过边e上的运算所得到的值。最后所有的边被删去，所剩顶点的值即为得分算法设计与分析46多边形游戏的表达设所有的边依次从1到n编号，按顺时针序列为op[1],v[1],op[2],v[2],…,op[n],v[n]

其中op[i]为边i上的运算符，v[i]为顶点i上的值。将多边形中始于顶点i(1≤i≤n)，长度为j的顺时针链v[i],op[i+1],…,v[i+j–1]表示为p(i,j)。若链p(i,j)最后一次合并在op[i+s](1≤s≤j–1)处发生，则被分割为两个子链p(i,s)和p(i+s,j–s)算法设计