动态规划讲稿.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,动态规划,什么是动态规划？,（一）动态规划是解决多阶段决策问题的一种方法。,多阶段决策问题,对于整个问题，可以根据其时间或其他顺序分成若干个前后相关联的子问题，问题的全局最优包含其子问题的局部最优，即满足最优子结构性质，并且无后效性，有边界条件，且一般划分为很明显的阶段，存在一条或多条状态转移方程。,图,1,D,A,G,C,K,B,N,P,O,M,J,F,H,E,L,I,3,1,2,3,4,5,2,1,4,3,2,3,1,4,2,2,1,2,2,2,3,3,4,4,阶段,1,阶段,2,阶段,3,阶段,4,阶段,5,任务：,P,是出发点，从,P,到,A,，,求最短路径,思路,先看第,5,阶段，到达,A,点有两条路,B,A,，,需要,2km,C A,，,需要,3km,令,从,P,A,的最短路径为,P(A),；,从,P B,的最短路径为,P(B),；,从,P,C,的最短路径为,P(C),P(A)=minP(B)+,2,P(C)+,3,；,P(B)=minP(D)+,1,P(E)+,2,；,P(C)=minP(E)+,5,P(F)+,4,；,P(A)=minP(B)+,2,P(C)+,3,；,P(B)=minP(D)+,1,P(E)+,2,；,P(C)=minP(E)+,5,P(F)+,4,；,D 1 B 2 A,2 3,5,P(B)E C,4,P(C),F,P(N)=2;,P(O)=3;,上述递推公式告诉我们，要求,P(A),需要先求出阶段,5,中的,P(B),和,P(C),；,要求,P(B)(,或者,P(C),），,又要先求出阶段,4,中的,P(D),和,P(E)(,或,P(F),和,P(E),显然，要依照上述递推过程求解，需要倒过来，从,P(P),出发，先求出第一阶段的,P(O),和,P(N),，,再求第二阶段的,P(K),，,P(L),，,P(M),；,，,最后得到,P(A),。,3,、选择数据结构，将每条路经的长度存在数组中。东西方向上的道路长度存在两维数组,h43,中规定数组的第一维为行号，第二维为列号。,3,1,2,3,4,5,2,1,4,3,2,3,h43=3,2,3,2,1,4,3,4,5,3,1,2;,0,1,2,1,0,2,3,南北方向上道路长度存至数组,v34,中，也规,定第一维为行号，第二维为列号。,0,1,2,3,2,1,0,2,2,3,4,4,1,2,4,1,2,2,3,v34=2,2,3,4,4,1,2,4,1,2,2,3;,为了计算方便，将图,1,改为图,2,h30,h31,h32,h20,h21,h22,h10,h11,h12,h00,h01,h02,v20,v21,v22,v23,v10,v11,v12,v13,v00,v01,v02,v03,(3,3),0,2,1,3,2,1,3,y,x,图,2,求解过程为从,(0,0),到,(3,3),求最短路径问题,定义二维数组，,P44=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,第一维为行，第二维为列。这时,P(O),为,P01,；,P(N),为,P10,；,P(A),为,P33,。,P00=0;,对于阶段,1,:,P01=P00+h00=0+3=3;,P10=P00+v00=0+2=3;,对于阶段,2,P11=min,P01+v01,P10+h10=min,3+1,2+2=4,P02=P01+h10=3+2=5,P20=P10+v10=2+4=6,分阶段递推求解过程,对于阶段,3,P12=min,P02+v02,P11+h11,=min,5+3,4+1=5,P03=P02+h02=5+3=8,P21=min,P11+v11,P20+h20,=min,4+1,6+1=5,P30=P20+v20=6+1=7,对于阶段,4,P13=min,P03+v03,P12+h12,=min,8+4,5+4=9,P22=min,P12+v12,P21+h21,=min,5+2,5+4=7,P31=min,P21+v21,P30+h30,=min,5+2,7+3=7,对于阶段,5,P23=min,P13+v13,P22+h22,=min,9+4,7+5=12,P32=min,P22+v22,P31+h31,=min,7+2,7+1=8,最后,P33=min,P23+v23,P32+h32,=min,12+3,8+2=10,综上，数组,P,的通项表示为,Pij=min(pi-1j+vi-1j),(pij-1+hij-1)(i,j0),P0j=P0j-1+h0j-1(i=0,j0),Pi0=Pi-10+vi-10(i0,j=0),“最优性原理”可陈述为：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。,最优决策序列的子序列，一定是局部最优决策子序列。,包含有非局部最优的决策子序列，一定不是最优决策序列。,最优性原理,如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以,4,的余数最小。,MOD 4,余数最小问题,设所有点从左至右编号为,14,，,MIN,（,i,）表示前,I,个点的最优值，很容易得出一个方程：,Min(i,)=min(Min(I-1)+numI-1,1)mod 4,Min(I-1)+numI-1,2)mod 4,通过这个方程可以求出一条路径为（,2+3+1,）,MOD 4=2,但最优值实际上是,（,2+1+1,）,MOD 4=0,。,为什么会出错呢？,分析,观察以上数据发现取,Min(,),的时候，动态规划求出来的最优值为，而正确的值应该为,0,，由此可知本题对应于一条最优路径，并不是这条路径上的所有点的最优值都是从点到该点可得的最优值，对于每一个阶段都取最优值并不能保证求出最优解，即不满足最优化原理，因此这种规划方法在本题行不通。,让我们来换一个思路思考本题，因为本题是要求总和除以余数最小的一条路径，我们先撇开最小余数不去管它，而是将本题改为从点,1,到点的所有路径中，求出每条路上权值和除以的不同余数的个数。,我们设一个数组,canI,j,表示从点,1,至点可不可以求出一条路径是该路径的权值总和除以的余数为，那么又可以得出一个方程：,canI,j,:=canI-1,k and(,k+numI,p,)mod 4=j)(0=k=3,1=pn)Or(JI)Then Max:=-1 ,当前位置不存在，最优值为,-1,Else,Begin,S1:=Max(I+1,j)+triangleI,j;,沿左斜线向下走,S2:=Max(I+1,j+1)+triangleI,j;,沿右斜线向下走,If s1s2 then Max:=s1 Else max:=s2;,选取最优走法,End;,End;,递归算法,由以上算法不难算出其时间复杂度为,2n,，而本题,N,最大为,100,，显然当,N,比较大时是无法在规定时间内出解的，但本题又很难找出理想的剪枝方法。,通过以下搜索树可以看出在求,Max(2,1),Max(2,2),的时候两次调用函数,Max(3,2),，也就是说，函数,Max(3,2),被重复计算了两次，其实在这棵搜索树中有很多结点都被重复计算了多次，程序时效显然就会大打折扣了，实际上这也是搜索之所以会效率低下的一大原因。既然知道了上述搜索算法效率低的原因。对于同一个函数值搜索多次是没有必要的，因此我们可以每求出一个函数的值便可将其用数组保存下来，到了下次要用的时候直接从数组里调出来用就可以了。这样时间复杂度一下子降成了,O(N*N),函数个数最多不超过,N*N,个。,Function,Max(I,J,:integer):,longint,;,从当前位置开始的可得的最优值,Var,s1,s2 :,Longint,;,记录从左右斜线向下走的可达的最优值,Begin,If,AI,j,-1 Then Begin ,函数,I,，,J,已求出，直接赋值即可,Max:=,AI,j,;,Exit;,End;,If(In)Or(JI)Then Max:=0 ,当前位置不存在，最优值为,0,Else,Begin,S1:=Max(I+1,j)+triangleI,j;,沿左斜线向下走,S2:=Max(I+1,j+1)+triangleI,j;,沿右斜线向下走,If s1s2 then,AI,j,:=s1 Else,AI,j,:=s2;,选取最优走法,Max:=,AI,j,;,记录该函数值,End;,End;,动态规划问题具有以下基本特征,：,1,、问题具有多阶段决策的特征。,2,、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。,3,、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态。,4,、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。,动态规划的基本模型,阶段：据空间顺序或时间顺序对问题的求解划分阶段。,状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。,决策：根据题意要求，对每个阶段所做出的某种选择性操作。,状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。,动态规划的几个概念,动态规划问题的一般解题步骤,1,、判断问题是否具有最优子结构性质，若不具备则不能用动态规划。,2,、把问题分成若干个子问题（分阶段）。,3,、建立状态转移方程（递推公式）。,4,、找出边界条件。,5,、将已知边界值带入方程。,6,、递推求解。,【,例,1】,棋盘路径问题,题目简介：,有一个,n*m,的棋盘，左下角为（,1,1,），右上角为（,n,m,），如图,1,。有一颗棋子，初始位置在（,1,1,），该棋子只能向右走或者向上走，问该棋子从（,1,1,）到（,n,m,）一共有几条路径？,输入：,两个整数,n,和,m,。,输出：,一个数，路径总数。,(,n,m,),(1,1),(,n,m,),(,n,m,),(,n,m,),对于这个题目，如果,n,m,比较小，那么我们完全可以用初学者比较熟悉的搜索算法，对每条路径进行枚举，达到终点后，路径总数加,1,，枚举完所有路径，然后输出路径总数便可。但通过这种方法，我们不难发现，不同的两条路径，完全有可能有相同的部分路径，如图,2,和图,3,。,(,n,m,),(,n,m,),(1,1),(4,2),(5,3),(,n,m,),(,n,m,),(,4,2,),(5,3),(1,1),在图,2,和图,3,中这两条不同的路径中，点（,1,1,）到点（,4,2,）这段路径和点（,5,3,）到点（,n,m,）这段路径被重复走过，不难想象，在枚举的过程中，必定有很多路径被重复走过。这样，势必造成程序运行时间的浪费，当,n,和,m,的值比较大的时候，程序很可能超时。,为了避免程序的重复运行，节省时间，我们可以通过记录点（,1,1,）到任意一个点（,i,j,）的路径总数来解决这个问题。假设,F(i,j),是点（,1,1,）到点（,i,j,）（,1in,）（,1jm,）的路径总数，因为棋子在棋盘中只能向右或者向上走，所以棋盘中只有,2,个点的棋子可以走到点（,i,j,），即点（,i,j-1,）和（,i-1,j,），这样，我们就可以知道，,F(i,j),的值必定是,F(i,j-1),和,F(i-1,j),的和，即：,F(i,j),F(i-1,j),F(i,j-1),因为,F(1,1),1,是显然的，所以，我们可以通过公式，推出,F(n,m),的值，,F(n,m),即点,(1,1),到点,(n,m),的路径总数。,以上的解题思路就是动态规划思想，在动态规划中，有两个概念比较重要，即状态和状态转移方程。在上面的例子中，,F(i,j),为状态，公式,F(i,j),F(i-1,j),F(i,j-1),为状态转移方程。对于这两个概念，我们将在以后继续讨论。,参考程序：,program exp1;,var,f:array0.100,0.100of integer;,i,j,n,m:integer;,begin,readln(n,m);,fillchar(f,sizeof(f),0);,f1,1:=1;,for i:=1 to n do,for j:=1 to m do,if i*j1 then,fi,j,:=fi-1,j+fi,j-1;,writeln(fn,m,);,end.,【,例,2】,拦截导弹问题（,NOIP1999,）,题目简介,:,某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。,输入导弹依次飞来的高度（雷达给出的高度数据是不大于,30000,的正整数），计算这套系统最多能拦截多少导弹，和如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。,样例：,input,389 207 155 300 299 170 158 65,output,6,解题思路：,本试题的实质是在一个数列中寻找递减的、未必连续的最长子序列。对于这个问题，我们可以从,n,出发，依次反向计算被拦截的导弹数。我们假设当导弹,i,作为被拦截导弹之一时，,Fi,为导弹,i,到导弹,n,序列中可以被拦截的最多导弹数。对于,Fi,的求解。我们可以这样考虑，对于所有导弹,j(i+1jn),，如果满足导弹,j,的高度，则判断最大的,Fj,值，,Fi,就是最大的,Fj,加上,1,，即：,Fi,:=,max(Fj,|,导弹,j,的高度导弹,i,的高度,),1,（,i+1jn,）,而一套系统能够拦截最多的导弹数,best,就是,max(Fi,),（,1in,）。对于这个例子，从动态规划算法的角度看，,Fi,是状态，公式,Fi,:=,max(Fj,|,导弹,j,的高度导弹,i,的高度,),1,（,i+1jn,）就是状态转移方程。,部分参考程序段：,best:=0;,fillchar(f,sizeof(f),0);,for i:=n,downto,1 do,begin,fi,:=1;,for j:=i+1 to n do,if(,aj,fi,)then,fi,:=fj+1;,ai,为第,i,枚导弹的高度,if,fi,best then best:=,fi,;,end;,【,例,3】,合唱队形（,NOIP2004,）,题目简介,:,N,位同学站成一排，音乐老师要请其中的,(N-K),位同学出列，使得剩下的,K,位同学排成合唱队形。,合唱队形是指这样的一种队形：设,K,位同学从左到右依次编号为,1,2,K,，他们的身高分别为,T1,T2,TK,，则他们的身高满足,T1Ti+1TK(1=i=K),。,你的任务是，已知所有,N,位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。,输入文件的第一行是一个整数,N,（,2=N=100,），表示同学的总数。第二行有,n,个整数，用空格分隔，第,i,个整数,Ti,（,130=Ti=230,）是第,i,位同学的身高（厘米）。,输出文件包括一行，这一行只包含一个整数，就是最少需要几位同学出列。,样例输入：,8,186,186,150 200 160 130 197 220,样例输出,4,解题思路：,该题目的实质和例,2,是一样的，其不同点在于这道题需要考虑两个满足题目要求的最长子序列。我们设,h,为身高序列，其中,hi,为同学,i,的身高。,设,F,为由左向右身高递增的人数序列，其中,Fi,为同学,1,到同学,i,间（包括同学,i,）身高满足递增顺序最多的人数。显然，通过和例,2,相同的思路，我们可以得到如下状态转移方程：,Fi,:=,maxFj,|,同学,j,的身高,同学,i,的身高,+1,（,1ji-1,）,同理，我们设,Gi,为同学,n,到同学,i,间（包括同学,i,）身高满足递增顺序最多的人数，得到如下状态转移方程：,Gi,:=,maxGj,|,同学,j,的身高,hj)and(fj+1,fi,)then,fi,:=fj+1;,end;,for i:=n,downto,1 do,begin,gi,:=1;,for j:=i+1 to n do,if(,hj,gi,)then,gi,:=gj+1;,end;,max:=0;,for i:=1 to n do,if,fi+gi,max then max:=,fi+gi,;,writeln(n-max+1);,通过以上例子，我们应该对动态规划有了一个初步的认识。动态规划算法思想在于子问题的计算结果，以供将来对相同子问题结果的随时调用，从而避免重复计算，节省时间。同时我们也看到，动态规划算法思想往往是将一个大问题,i,，转化为一个类拟的小问题,i-1,，我们将问题,i,称之为阶段,i,，把阶段,Fi,的值叫做这个阶段的状态。而阶段,i,转换为阶段,(i-1),时，我们把状态,Fi,转化为状态,Fi-1,的公式称之为状态转移方程。所以，我们在用动态规划算法解决问题时，关键是如何定义状态,Fi,和如产生正确的状态转移方程这两个方面，这方面的能力就需要同学们在平时的训练中通过慢慢体会逐步提高。,现在我们来考虑用动态规划算法解决问题的条件。,1,、无后效性,在,OI,试题中，并不是所有的问题都可以用动态规划来解决，比如例,1,，如果我们把题目改成棋子可以向上、下、左、右四个方向走动，那么例,1,中使用的状态转移方程,F(i,j),F(i-1,j),F(i,j-1),便不成立了。因为走到点,(,i,j,),的路径不光只是通过点,(i-1,j),和点,(i,j-1),，还有,(i+1,j),和,(i,j+1),，而点,(i+1,j),和,(i,j+1),的路径数还需要通过点,(,i,j,),来计算，这样就产生了一个冲突。简单地说，就是后面产生的值影响了前面的结果。所以我们要提出动态规划的约束条件：无后效性。无后效性指将各阶段按照一定的次序排列好之后，对于阶段,i,的状态只能由阶段,i-1,的状态通过状态转移方程得来，与其它状态无关，尤其是对未发生的状态没有关系。,2,、最优化原理,动态规划的第二个约束条件是最优化原理。最优化原理要求将问题转化为较小的子问题时，子问题必须具备最优子结构。即阶段,i-1,的最优解,Fi-1,决定了阶段,i,的最优,Fi,，依次类推产生全局的最优解。如果局部的最优解不能产生全局的最优解，或者全局的最优解并不是通过局部的最优解推导产生，则我们称这类问题不具有最优子结构，当然也不适合用动态规划算法来解决问题。,线性规划模型,例,1,：机器分配问题。,总公司拥有高效生产设备,M,台，准备分给下属的,N,个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这,M,台设备才能使国家得到的盈利最大？求出最大盈利值。其中,M,=150,，,N=100,。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数,M,。,数据文件格式为：第一行保存两个数，第一个数是设备台数,M,，,第二个数是分公司数,N,。,接下来是一个,N*M,的矩阵，表明了第,I,个公司分配,J,台机器的盈利。,分析,用机器数来做状态，数组,FI,，,J,表示前,I,个公司分配,J,台机器的最大盈利。则状态转移方程为,:,FI,，,J=MaxFI-1,，,K+ValueI,，,J-K(1=I=N,1=J=M,0,=K=J),初始值,:F(0,0)=0,时间复杂度,O(N*M,2,),最长不下降序列,设有整数序列,b1,b2,b3,bm,，,若存在下标,i1i2i3 in,，且,b,i1,b,i2,b,i3,b,in,，,则称,b1,b2,b3,bm,中有长度为,n,的不下降序列,b,i1,b,i2,b,i3,b,in,。,求序列,b1,b2,b3,bm,中所有长度,(n),最大不下降子序列,输入：整数序列。,输出：最大长度,n,和所有长度为,n,的序列个数,。,分析,（,1,）设,f,(i),为前,i,个数中的最大不下降序列长度,则,f(i)=maxf(j)+1 (1=ji,=m,bj,bi),边界为,F(1)=1,(2),设,t,(i,),为前,i,个数中最长不下降序列的个数,则,t(i,)=,t(j,)(,1=ji,=m,bj,bi,f(i,)=f(j)+1),初始为,t,(i,)=1,当,f(i,)=n,时，将,t(i,),累加,举例：,1 2 3 4 6 5 8 10 9,f:1 2 3 4 5 5 6 7 7,t:1 1 1 1 1 1 2 2 2,答案：,f=7,时，,边界为,t,=4,进一步,(3),求本质不同的最长上升序列个数有多少个？,如：,1 2 3 4 6 5 8 10 9,有，,1 2 3 4 6 8 10,1 2 3 4 5 8 10,1 2 3 4 6 8 9,1 2 3 4 5 8 9,都是本质不同的。,但对于,1 2 2 3 3 5 4,f 1 2 2 3 3 4 4,t 1 1 1 2 2 4 4,答案有,8,个，其中,4,个,1 2 3 5,，,4,个,1 2 3 4,改进算法,上例显然对于两个相同的数，重复算了多次,因此，我们对算法进行改进：,对原序列按,b,从小到大（当,bi=,bj,时按,F,从大到小）排序，增设,Order(i),记录新序列中第,i,个数在原序列中的位置。可见，,求,t(i),时，当,f,(j)=f(j+1),b(j)=b(j+1),且,Order(j+1)Order(i),时，便不累加,t(j),。,这样就避免了重复。,上述算法的时间复杂度为,O(n,2,),有一条河从东向西将某地区分为南北,2,个部分。河的两岸各有,N,个城市。北岸的每个城市都与南岸的某个城市是友好城市，而且关系是一一对应的。现在要求在,2,个友好城市之间建立一条航线，但由于天气的缘故，所有的航线都不能相交，因此，就不能给所有的友好城市建立友好航线。请设计一个修建航线的方案，能建最多的航线而且不相交。,输入：,第一行为一个正整数,N(N=1000),以下,N,行，记第,i,行有一个正整数,j,，,表示北岸的城市,i,与南岸的城市,j,互为友好城市。其中城市编号是按从东到西排列的。,输出：,仅一行，即最多的航线数。,船,(,ceoi,),首先我们需要判定对于给定的两条航线是否相交，设北岸城市,i1,，,j1(i1 j1),分别与南岸城市,i2,，,j2,互为友好城市，那么这两条航线不相交,(,以下简称为,i1,，,j1,相容,),的充要条件是,I2=J2,。,(,结论,1),由下图就可以很容易地得到这个结论。,i1,j2,i2,j1,j2,i2,j1,i1,北岸：,南岸：,图,一,图,二,分析,从上面的结论可以看出，最优的选择方案中，如果将所有航线按北岸村庄号从小到大排序，序列中每一个北岸村庄对应的南岸村庄号必然满足,B1B2B3,Bn,（,n,为选出来的航线数）。,同样，对于任一个方案，如果北岸村庄排好序后，与之对应的南岸村庄也是按升序排列，那么该方案必然不存在相交的两条航线；相反，如果南岸村庄不是按升序排列，必存在两条相交的航线。因此，我们可以先将各航线按北岸村庄号排一个序，那么最优的方案必然是从相对应的南岸村庄中找出一个最长不下降序列，该序列的长度即为问题的解。,凸多边形三角划分,给定一个具有,N,（,N50,）,个顶点（从,1,到,N,编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成,N-2,个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？,输入文件：第一行 顶点数,N,第二行,N,个顶点（从,1,到,N,）,的权值,输出格式：最小的和的值,各三角形组成的方式,输入示例：,5,122 123 245 231,输出示例：,The minimum is,：,12214884,The formation of 3 triangle:,3 4 5,1 5 3,1 2 3,分析,设,FI,J,（,IJ,）,表示从顶点,I,到顶点,J,的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：,FI,J=MinFI,K+FK,J+SI*SJ*SK (0IKJ=N),初始条件,:F1,，,2=0,目标状态,:,F1,N,但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算,在数字串中插入若干,(K,个,),乘号使总的乘积最大。,分析：定义 从,l,到,r,加入,k,个乘号的最大乘,积值为,p(l,r,k),。,p(,l,r,k,)=max d(l,q)*p(q+1,r,k-1),数字最大乘积,解题思路,定义,:,从,l,到,r,加入,k,个乘号的最大乘,积值,p(l,r,k),。,p(,l,r,k,)=max d(l,q)*p(q+1,r,k-1),动态规划模型的建立,1,、一般动态规划,某些问题在状态的选择上会遇到一些困难，,但困难更多的集中表现在阶段的划分上，因,为阶段的特征并不明显。在这种情况下，通,常按状态最优值的大小划分阶段，并采用类,似搜索的方法解状态转移方程。,例题,1,：骨牌游戏,一张骨牌可被分为两个正方形。每个正方形为空或有,1,至,6,个点。如下图,上面的一排正方形点数总和为,6+1+1+1=9,，底下一排的点数为,1+5+3+2=11,。上部和底部之差为,2,。任一张骨牌能被转动,180,，保持其正面始终朝上。,为了使骨牌上下点数之差最少，求所需旋转的次数最少为多少？,(,骨牌张数,n=1000),例如上图，至多只需将最后一张骨牌旋转一次，便能使差值为,0,，因此在此情况下，答案为,1,。,从问题的规模看，这一题肯定不是用搜索解决。我们不妨先不考虑最少旋转次数，而是找出一个使上下两行绝对值差最小的方案。也许有人会想到用,FI,表示前,I,张骨牌能够成的最小差值，构造一个动态规划方程来解决该问题。但只要细想就会发现，该问题用这种方式规划不满足最优性原理，用这种形式的动态规划实际上是一种贪心，有反例！注意到骨牌上的点数范围很小，只可取,0,到,6,，因此，我们可以采用一种类似于枚举的动态规划。,用,FI,，,J,表示前,I,张骨牌能否构造出上下差为,J,的方案。于是我们可以列出如下动态转移方程：,fI,j,=,fI,1,j (,aI,bI,)or,fI,1,j (,bI,-,aI,),其中,AI,、,BI,分别表示第,I,张骨牌最初上下两面的点数。对应的两种转移方式则分别表示第,I,张骨牌翻动与第,I,张骨牌不翻动的情况。,边界：,f0,0=True,至于最后求出的最少差值，只要从,Fn,，,j,中寻找一个可以取到的绝对最小的,J,即可。,由于,n,最大为,1000,，骨牌上的点数为,0,到,6,，所以最小差值的范围也只是,-6000,到,6000,，该算法在最坏的情况下要计算,1000*12000,次，时间效率比起搜索，要快很多。,现在的问题是如何求出最少翻动的骨牌数。受到前面方程的启发，我们可以重新定义一下,F,数组，用,FI,，,J,表示前,I,张骨牌构成差值,J,要翻动的最小骨牌数。类似的，我们可以列出如下方程：,fI,j,=,minfI,1,j (,aI,bI,),fI,1,j (,bI,aI,)+1,由于第一种选择不翻动第,I,张骨牌，所以最小翻动次数在原基础上不变。而第二种选择要翻动骨牌,I,，所以最小翻动次数要加,1,。,边界：,f0,0=0,在程序的具体实现时，将整个,F,数组的值都赋成一个足够大的数,MAX,，不难想到，如果用前,I,张骨牌不可构成差值,J,，最后,FI,，,J,的值一定为,MAX,。要求出最小差值和最小翻动次数，只要从,FN,，,J,中选出一个不为,max,，且绝对值最小的,J,，选出的,J,对应的,FI,，,J,的值即为问题的解。,因为问题的处理涉及到绝对值，所以如果,FI,，,J,与,FI,，,-J,的情况都有可能取到，我们应该从这两个量中选出一个小的作为最小翻动骨牌数。,动态规划模型的建立,2,、多次动态规划,有些问题的求解过程对应多个状态转移方程；或者虽对应一个状态转移方程，但由于内存空间限制，一次动态规划仅能计算出最优解的值，无法构造最优解的形成过程。在这种情况下，需要进行多次动态规划。,最长公共子串问题,有两个字符串,A,，,B,，当存在一个严格递增的整数序列,i,1,，,i,2,，,，,i,m,，满足,a,1,=b,i1,，,a2=b,i2,，,，,a,m,=,b,im,，我们则说,A,包含于,B,。例如，“,adg,”,包含于“,abcdefg,”,，而不包含于“,gfedcba,”,。现在有三个字符串,A,，,B,，,C,，要求你找出一个满足以下条件的最长的字符串,D,。,D,包含于,A,；,D,包含于,B,；,D,包含于,C,。输入：,A,，,B,，,C,。输出：,D,。,分析,首先，定义一个字串“前缀”的概念：,给定一个字串,s=s,1,s,m,。对于,I=0.m,，定义,s,的第,I,个前缀为,s,I,=s,1,s,i,。三个输入串,A,，,B,，,C,的所有前缀组成了最长公共子串的子问题空间。由此，我们发现最长公共子串的最优子结构性质。,设：,A=a,1,，,，,a,m,；,B=b,1,，,，,b,n,；,C=c,1,，,，,c,h,。,A,，,B,，,C,的最长公共子串为,D=d,1,，,，,d,k,，,D,的长度为,k,。,性质,1,：,a,m,=,b,n,=,c,h,，则,d,k,=a,m,=,b,n,=,c,h,且,d,k-1,是,a,m-1,，,b,n-1,，,c,h-1,的一个最长公共子串。,性质,2,：,a,m,b,n,，,a,m,c,h,，,b,n,=,c,h,，则,d,k,a,m,，蕴含,D,是,a,m-1,和,B,、,C,的一个最长公共子串。,性质,3,：,b,n,a,m,，,b,n,c,h,，,a,m,=,c,h,，则,d,k,b,n,，蕴含,D,是,b,n-1,和,A,、,C,的一个最长公共子串。,性质,4,：,c,h,a,m,，,c,h,b,n,，,a,m,=,b,n,，则,d,k,c,h,，蕴含,D,是,c,h-1,和,A,、,B,的一个最长公共子串。,由此可见，字串,A,、,B,和,C,的最长公共字串包含了三个字串前缀的最长公共字串，说明该问题具备最优子结构的性质。,设,fI,，,j,，,k,为,a,i,，,b,j,，,c,k,的一个最长公共子串的长度（,0im,，,0jn,，,0kh,）。,fm,，,n,，,h,为问题的解,.,则状态转移方程为：,当（,j=0,）,or,（,k=0,）时，,fI,，,j,，,k=0,；,当（,a,i,=,b,j,=c,k,）时，,fI,，,j,，,k=fI-1,，,j-1,，,k-1+1,；,当（,a,i,b,j,）或（,b,j,c,k,）时，,fI,，,j,，,k=maxfI-1,，,j,，,k,，,fI,，,j-1,，,k,，,fI,，,j,，,k-1,。,由于,A,，,B,，,C,三个字串的长度上限为,100,，因此约需要,1M,内存存贮,f,数组，这是静态数据区（,640k,）根本无法容纳的。为此：,（,1,）采用指针类型：,fIj,，,k,；,（,2,）及时收回内存：由于计算,fI,时，只需要,fI-1,，因此可及时释放内存空间。,（,3,）进行两次动态程序设计：由于,f1fI-2,已释放，无法根据状态转移方程构造完整的最长公共子串，因此必须进行两次动态规划：,第一次动态方程设计，根据,fr,fm,构造,a,r,a,m,中所含的最长公共子串。,第二次动态程序设计，根据,f1fI-2,构造,a,1,a,r-1,中所含的最长公共子串，并与第一次动态规划产生的公共子串拼接，形成完整的公共子串,D,。,动态规划时间效率的优化,一、减少状态总数,1,、改进状态表示,状态的规模与状态表示的方法密切相关，通过改进状态表示减小状态总数是应用较为普遍的一种方法。,有一批编号为,1,至,N,且尺寸规格一样的箱子。现在要将其中某些箱子叠放起来，使叠放的高度最大，箱子叠放的规则如下：,一、每个箱子上最多只能直接叠放一个箱子；,二、编号较小的箱子不能放在编号较大的箱子之上；,三、每个箱子都给出了,自身重量,与,可承受重量,，每个箱子上的所有箱子重量之和不得超过该箱的可承受重量。,输入箱子数,N,（,1N1000,）及每个箱子的自身重量与可承受重量，两个数值均为小于等于,3000,的正整数。输出最多可叠放的箱子总数,M,和每个箱子的编号。,例题,3,：叠放箱子,箱子是按编号顺序叠放，所以可用动态规划求解。设：,WeightI,表示第,I,个箱子的重量。,SupportI,表示第,I,个箱子的承受重量。,F(i,j,),表示前,i,个箱子中最多可选出,f(i,j,),个叠放，还可承受重量,j,。,F(i,j,)=Max F(i-1,j+Weighti)+1,F(i-1,j),。,（其中，,J3,时：,mi,j=,mi,j OR mi+1,j-i*k (1kai),规划的边界条件为：,mi,0=true,；,0i7,若存在,k,，使得,m3,k=true,m4,Mid-k=true,，则,可以实现题目要求，否则无法实现。,回顾本题的优化过程可以发现：本题的实际背景与双向搜,索的背景十分相似，同样有庞大的状态空间，有确定的初始,状态和目标状态，状态量都迅速增长，而且可以实现交汇的,判断。,从本题的优化过程，我们认识到，双向扩展以减少状态,量的方法不仅适用于搜索，同样适用于动态规划。这种在不,同解题方法中，寻找共通的属性，从而借用相同的优化思想，,可以使我们不断创造出新的方法。,动态规划时间效率的优化,二、减少每个状态转移的状态数,在使用动态规划方法解题时，对当前状态,的计算都是进行一些决策并引用相应的已经计算过,的状态，这个过程称为“状态转移”。因此，每个状,态可能转移的状态数是决定动态规划算法时间复杂度,的一个重要因素。,动态规划时间效率的优化,1,、决策量的优化,分析问题最优解的性质，缩小决策集合，也,可以减少每个状态可能转移的状态数。,NOI96,中的添加号问题，是从“所得的和最小”,这一原则出发，仅在等分点的附近添加号，从而,大大减少了每个状态转移的状态数，降低了算法,的时间复杂度。,动态规划时间效率的优化,在一个操场上摆放着一排,n,（,n20,）堆石,子。现要将石子有次序地合并成一堆。规定,每次只能选相邻的,2,堆石子合并成新的一堆，,并将新的一堆石子数记为该次合并的得分。,试编程求出将,n,堆石子合并成一堆的最小,得分和最大得分以及相应的合并方案。,例题,5,：,石子归并,设,n,堆石子依次编号为,1,，,2,，,.,，,n,。各堆石子数,为,d1.n,，则动态规划的状态表示为：,mi,j,，,1ijn,，表示合并,di.j,所得到的,最大得分，则状态转移方程和边界条件为：,mi,j,=0,i=j,算法分析,i,j,该算法的时间复杂度为,O(n,3,),。,令,si,j,=k,，表示合并的断开位置，可以发现：,si,j,要么等于,i+1,，要么等于,j,。,于是，状态转移方程优化为：,mi,j,=0 i=j,MI,，,J=MAXMI,，,J-1,，,MI+1,，,J,）,+i,j,优化后每个状态转移的状态数减少为,O(1),，算法总的时间复杂度也降为,O(n,2,),。,2,、合理组织状态,在动态规划求解的过程中，需要不断地引用已经计算过的状态。因此，合理地组织已经计算出的状态有利于提高动态规划的时间效率。,动态规划时间效率的优化,给出一个由,n,个数组成的序列,x1.n,，找出它的最长单调上升子序列。,即求最大的,m,和,a1,a2,am,