动态程序设计

1、动态程序设计动态程序设计 动态规划是解决多阶段决策最优化问题的一种思动态规划是解决多阶段决策最优化问题的一种思想方法。所谓想方法。所谓“动态动态”，指的是在问题的多阶段，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。的决策序列在符合某种条件下达到最优。 动态程序设计是一种重要的程序设计思想，具有广泛的应用价值。使用动态规划思想来设计算法

2、，对于不少问题往往具有高时效，因而，对于能够使用动态程序设计思想来解决的问题，使用动态规划是比较明智的选择。 最短路径问题最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiSx为城市x到城市E的最短路径长度（x表示任意一个城市）；mapi，j表示i，j两个城市间的距离，若mapi，j=0，则两个城市不通； 思路：由后往前依次推出每个思路：由后往前依次推出每个DisDis值，直到推出值，直到推出DisDisa a为止。为止。所谓前后关系是指对于任意一对

3、城市i和j来说，如果满足“或者城市i和城市j不连通或者disi+mapi，jdisj”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Disimapi，jDisj，则说明城市j至城市E的最短路径长度应该比Disj更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何划分先后次序呢？我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系diskx=dis4E=0 k=4，3，0，其中diskx指k阶段的城市x。由此得出程序 disE0； for k3 downto 0 do for x

4、取遍k阶段的所有城市do begin disx； for y取遍k+1阶段的所有城市do if disy+mapx,yfmaxi,j 计算将ai、ai+1、aj划分成p个部分的状态转移方程 t h e n f m a x i , j : = f m a x 1 i , k * g k + 1 , j ; if(fmin1i,k=0)and(fmin1i,k*gk+1,jfmini,j)or(fmini,j0)then fmini,j:=fmin1i,k*gk+1,j; end;for fmin1:=fmin;fmax1:=fmax; end;formax:=0;min:=maxlongint;

5、将a1、a2、an划分成m个部分的最大值和最小值初始化if m=1 计算n个数划分成一部分的最大值和最小值 then begin max:=g1,n;min:=g1,n;endthen else for i:=1 to n do将a1ai-1、aj+1an设为第m部分，计算最大值和最小值 for j:=i to n do if (i1) or (jn) then begin if(g1,i-1+gj+1,n)mod mask*fmax1i,jmax thenmax:=(g1,i-1+gj+1,n)mod mask*fmax1i,j; if(fmin1i,j=0) and (g1,i-1+gj+

6、1,n) mod mask*fmin1i,jr then search:=1 else begin if fl,r=flag then若尚未计算出顶点l顶点r对应子树的最高分值 for i:=l to r do begin 枚举每一个可能的子根i n o w : = s e a r c h ( l , i -1)*search(i+1,r)+fi,i;计算以i为根的子树的分值 if nowfl,r then若该分值为目前最高，则记入状态转移方程，并记下子根 begin fl,r:=now;wayl,r:=i; end;then end;for search:=fl,r;返回顶点l顶点r对应子树

7、的最高分值 end;elseend; search 显然主程序可以通过递归调用search(1,n)计算最高分值。算法的时间复杂度为O(n3) 2、输出加分二叉树的前序遍历、输出加分二叉树的前序遍历procedure writeout(l,r : integer);前序遍历顶点l顶点r对应的子树 begin if lr then exit; if firstwrite then firstwrite:=false else write( );顶点间空格分开 write(wayl,r);输出子根 writeout(l,wayl,r-1); 前序遍历左子树 writeout(wayl,r+1,r)

8、;前序遍历右子树 end;writeout主程序主程序 read(n);读顶点数 for i:=1 to n do状态转移方程初始化 for j:=i to n do fi,j:=-1; for i:=1 to n do begin read(temp);读顶点i的分值 fi,i:=temp;wayi,i:=i;顶点i单独成一棵子树 end;for writeln(search(1,n);计算和输出最高加分 firstwrite:=true;设立首顶点标志 writeout(1,n);前序遍历二叉树 writeln;一、回溯法回溯法+ +动态程序设计解动态程序设计解题题 有些题需要在动态程序设

9、计前通过搜索计算决策代价,即通过回溯法+动态程序设计解题火柴游戏火柴游戏 有红，绿，蓝三种颜色的火柴，所有火柴长度一样。用它们可以组成一些数字， 如下图所示： 为了让组成的火柴好看一些，我们规定：有公共点的火柴必须不同色。例如，用红火柴4根和蓝火柴3根可以组成数12，21，7等。而且有些方案虽然数字和它们的排列顺序都相同，但是有颜色之分。问：一共可以组成多少个数（可以包含多个数字，但至少包含一个数字）？同一个数用不同颜色表示算作不同的数，火柴可以有剩余。 输入输入 三个整数n1， n2， n3 (0 n1，n2，n3 15)，即三种颜色的火柴的数目。 输出输出 仅一个数，即可以组成的数的数目。

10、结果保证不超过1016。 本题是组合计数问题，有经验的选手一看就知道是用动态规划，但是具体怎么做呢？假设使用a根红火柴，b根绿火柴和c根蓝火柴能组成的单个数字个数为counta， b， c，用da，b，c表示用a根红火柴，b根绿火柴和c根蓝火柴可以组成的数串的个数（包括空串），则递推式为： di，j，k = sumdi-a， j-b， k-c * counta， b， c + 1 (i=a， j=b， k=c) 由于题目不允许空串，因此最后答案为dn1， n2， n3 1。问题的关键就是如何求counta， b， c。注意到每个数字最多只能使用同色的火柴三根，因此0a，b，c3，我们可以用搜索

11、来求出所有的counta， b， c。在参考程序中，我们用digit数组记录每个数字需要用到哪些位置的火柴，adj数组记录每个位置的相邻位置集合，则搜索过程定义为： search(depth， c1， c2， c3) 其中depth是深度，即当前考虑的火柴编号，c1， c2， c3为已经使用过的三种颜色的火柴数目。本题是搜索和动态规划的综合题目，同时考察了常量数组在简化程序方面的运用。本题程序是这次模拟题中最长的，但是只要耐心加细心，要完成这道题目并不困难。 const adj：array1.7，1.4 of integer=( (2，4，0，0)，(1，3，5，0)，(2，4，5，7)，(1

12、，3，7，0)，(2，3，6，0)，(5，7，0，0)，(3，4，6，0)； adjiI，j为i位置j方向的相邻位置 digit：array0.9，1.7 of integer=( (1，2，4，5，6，7，0)，(4，7，0，0，0，0，0)， (1，3，4，5，6，0，0)， (1，3，4，6，7，0，0)， (2，3，4，7，0，0，0)，(1，2，3，6，7，0，0)， (1，2，3，5，6，7，0)，(1，4，7，0，0，0，0)， (1，2，3，4，5，6，7)，(1，2，3，4，6，7，0)；digiti，j为数字i中第j根火柴的位置 var count ： array0.3，0

13、.3，0.3 of integer； 使用a根红火柴，b根绿火柴和c根蓝火柴能组成的单个数字个数为counta， b， c d：array0.15，0.15，0.15 of extended； da，b，c表示用a根红火柴，b根绿火柴和c根蓝火柴可以组成的数串的个数（包括空串） n1，n2，n3：integer；procedure dp； 动态程序设计var i， j， k， a， b， c ： integer；beginfor i ：= 0 to n1 do 枚举数串中三种颜色火柴的所有可能组合 for j ：= 0 to n2 do for k ：= 0 to n3 do begin di

14、， j， k ：= 1； for a ：= 0 to 3 do 枚举单个数字中三种颜色火柴的所有可能组合 for b ：= 0 to 3 do for c ：= 0 to 3 do若a根红火柴、b根绿火柴和c根蓝火柴能构成一个数字，则累计 if (i = a) and (j = b) and (k = c) then di， j， k ：= di， j， k + counta， b， c * di - a， j - b， k - c； end； writeln(dn1，n2，n3 - 1 ： 0 ： 0)；输出n1， n2， n3(三种颜色的火柴数)可以组成的数的数目end； begin fi

15、llchar(count， sizeof(count)， 0) 单个数字的个数序列初始化 for num ：= 0 to 9 do 依次计算每一个数字的构成方案 begin fillchar(color， sizeof(color)， 0); try(1， 0， 0， 0)； 递归计算数字num的方案数 end；for end；generate begin generate；计算数字09的方案数 read(n1， n2， n3)； 输入三种颜色的火柴数目 dp；动态规划 end.main二、计算所有方案二、计算所有方案 对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态程序设计方法呢？

16、如果我们可以找出状态转移的关系，并在状态转移方程中去掉最佳性要求opt（min或max），将扩展子状态的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。显然，在计数类问题中使用这种方法要比回溯法等搜索算法简捷许多。kkkkksDukkuusTfgsfkkk,),(opt)(1)(骑士游历问题骑士游历问题设有一个n*m的棋盘(2n50，2m50)，如下图。在棋盘上任一点有一个中国象棋马，马走的规则为：1.马走日字 2.马只能向右走。即左图所示：当n，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：(n=10，m=10)，(1，5)(起点)，

17、(3，5)(终点)。应输出2(即由(1，5)到(3，5)共有2条路径，如下图)：输入：输入：n，m，x1，y1，x2，y2(分别表示n，m，起点坐标，终点坐标)输出：输出：路径数目(若不存在从起点到终点的路径，输出0) 从(x1，y1)出发，按照由左而右的顺序定义阶段的方向。位于（x，y）左方且可达（x，y）的跳马位置集合都是（x，y）的子问题，起点至（x，y）的路径数实际上等于起点至这些位置集的路径数之和（如下图）。如此一来，状态转移关系便凸显出来。设状态转移方程map，其中mapi，j为起点（x1，y1）至（i，j）的路径数目。由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此

18、不妨设map数组的元素类型为extended。初始时，除mapx1，y1=1外其余为。显然。我们采用动态程序设计的方法计算起点（x1，y1）至终点（x2，y2）的路径数目mapx2，y2：阶段j：中国象棋马当前的列位置(y1jy2)；状态i：中国象棋马在j列的行位置（1in）；决策k：中国象棋马在（i，j）的起跳方向(1k4)； ),( ,),),(在界内的坐标集可达（yxyxmapjimapyxmapyxjibegin中国象棋马由（i，j）出发，沿着k方向跳至（x，y）；if (x.n)(y1.y2) 计算状态转移方程then mapx，y mapi，j+mapx，yend；forwrite

19、ln(mapx2，y2：0：0)；输出从（x1，y1）到（x2，y2）的路径数目fillchar(map，sizeof(map)，0)；mapx1，y1 1；从（x1，y1）出发for jy1 to y2 do 递推中国象棋马的列位置 for i1 to n do 递推中国象棋马在j列的行位置 for k1 to 4 do 递推中国象棋马在（i，j）的4个跳动方向过河卒过河卒 如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。 同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制8个点（图

20、中的P1，P2.P8）。卒不能通过对方马的控制点。 棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：CA，同时CB）。现在要求你计算出卒从A 点能够到达B点的路径的条数。 输输 入：入： 键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y）输输 出：出： 屏幕输出一个整数（路径的条数）。输入输出样例：输入输出样例： 输入：3 3 2 2 输出：01 1、计算对方马的控制点、计算对方马的控制点按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马

21、的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（显然，若（0，0）或（）或（n,m）为控制点，则输出路径数为）为控制点，则输出路径数为0。设。设constconstmove:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)2,-1)

22、； movek movek，1.21.2为马沿为马沿k k方向跳跃一步的水平增量和垂直增量方向跳跃一步的水平增量和垂直增量 varvarlist:array-1.20,-1.20 of complist:array-1.20,-1.20 of comp； 路径数序列，其中路径数序列，其中listi,jlisti,j为卒从为卒从(0,0)(0,0)到到(i,j)(i,j)的路的路径数径数 can:array0.20,0.20 of booleancan:array0.20,0.20 of boolean； 点点(i,j)(i,j)允许卒通行的标志允许卒通行的标志 马的初始位置为（马的初始位置为（

23、x,yx,y）。我们按照下述方式计算）。我们按照下述方式计算cancan序列：序列：canx,ycanx,y falsefalse； 对方马所在的点为控制点对方马所在的点为控制点 for ifor i1 to 8 do begin1 to 8 do begin从（从（x x，y y）出发，沿）出发，沿8 8个跳马方向计算控制点个跳马方向计算控制点 j jx+movei,1x+movei,1； 计算计算i i方向的跳马位置方向的跳马位置(j(j，k)k)k ky+movei,2y+movei,2；if (j=0) and (k=0) and (j=n) and (k=0) and (k=0) a

24、nd (j=n) and (k0) and (map k，b0) Then 如果a与k，k与b均可达 if (mapa，b=0)or (mapa，bmapa，k+mapk，b) Then 如果a、b不可达，或者a、b之间的路径不如a-k-b这条路径短，则改变mapa，b的值 mapa，bmapa，k+mapk，b；注：mapa，b为从a到b的最短路的距离，如果a，b不可达，则mapa，b=0。 这个解题方法实质上就是一个动态程序设计方法。它是以最短路中间结点的取值来划分阶段的,第k个阶段为所有最短路的中间结点k时的情况。而第k个阶段只与前(k-1)个阶段有关系，所以，这个问题同时满足“无后效性

25、”与“最优子问题”这两个性质，采用动态程序设计方法是正确的。双重动态程序设计是在floyd-Warshall算法的基础是提出来的。 城市交通城市交通某城市有n（1n50）个街区，某些街区由公共汽车线路相连，如在下图中，街区1，2有一条公共汽车线路相连，且由街区1至街区2的时间为34分钟。由于街区与街区之间的距离较近，与等车时间相比可忽略不记，所以这个时间为两趟公共汽车的间隔时间，即平均的等车时间。由街区1至街区5的最快走法为1-3-5，总时间为44分钟。现在市政府为了提高城市交通质量，决定加开m(1m10)条公共汽车线路。若在某两个街区a，b之间加开线路（前提是a、b之间必须已有线路），则从a

26、到b的旅行时间缩小为原来的一半（距离未变，只是等车的时间缩短了一半）。例如，若在1，2之间加开一条线路，则时间变为17分钟，加开两条线路，时间变为8.5分钟，以此类推。所有的线路都是环路，即如果由1至2的时间变为17分钟，则由2至1的时间也变为17分钟。求加开某些线路，能使由城市1至城市n的时间最少。例如，在上图中，如果m=2，则改变1-3，3-5的线路，总的时间可以减少为22分钟。输入：输入： 第一行为城市数n与加开线路数m；第二行至第n+1行，每行为n个实数，第i+1行第j列表示由城市i到城市j的时间。如果时间为0，则城市i不可能到城市j。注意：输入数据中，从城市1到城市n至少有一条路线。

27、输出：输出： 第一行为由城市1到城市n的最小时间X（保留小数点后两位）；第二行至第m+1行为更改的线路。每行由两个整数（x，y）构成。表示将城市x与城市y之间增加一条线路。1、将道路a-b上增加的m条边可以分为如下两个问题（如果k是最短路上的一点） 求a-k增加t条边； 求k-b增加m-t条边。t可以取从0至m的任意值。问题a-b增加m条边的最优解取决与这两个子问题的最优解。2、在求m条边的过程中，始终只与增加t条边与增加m-t条边的子问题发生联系。系。 以上两个特点即为“无后效性”与“最优子问题”。所以，“城市交通”问题可采用动态程序设计方法。设vala，b，m的值为增加m条线路后城市a到城

28、市b的最短路长。其中vala，b，0的值为原交通图中边城市a至城市b的最短路，可以直接使用floyd算法计算；vala，b，m=minvala，k，t+valk，b，m-t(其中t为从0到m中的一个数，k为a到b中间的一点)直接使用floyd算法计算vala，b，0（1an，1bn）；for g1 to m do 按照新增加的边数g划分阶段 begin 对任一对城市（i，j）来说，(i，j)的边权减半；vali，j，g= (i，j)的边权； for k1 to n do 枚举中间城市 for i1 to n do 枚举经由城市k的所有城市对（ikj）for j1 to n do begin v

29、ali，j，g= ；计算状态转移方程 vali，j，g=minvali，j，g，vali，k，0+valk，j，gvalk，j，g0，valk，j，0+vali，k，gvali，k，g0 ；End；forend；for说明：这个问题的val数组的初始值与上一个floyd算法不一样，初始值均为maxint。这个算法的时间复杂度为W(n3*m2)，约为W(n5) ,),min0tkjkvaltkivalgt五、多进程的最优化决策问题五、多进程的最优化决策问题怎样对多个并行的、可划分阶段的进程进行最优化决策，关键是如何存储状态。多进程问题的状态数目十分庞大，每一个状态的存储量大，且又是求多条最佳路径

30、，这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。方格取数方格取数设有n*n的方格图（），我们将其中的某些方格中填入正整数，而其他的方格中则放入数字。如下图所示（见样例）：某人从图的左上角的点出发，可以向下行走，也可以向右走，直到到达右下角的点。在走过的路上，它可以取走方格中的数（取走后的方格中将变为数字）。此人从点到点共走两次，试找出条这样的路径，使得取得的数之和最大。输入：输入的第一行为一个整数（表示的方格图），接下来的每行右三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的表示输入结束。输出：只需输出一个整数，表示条路径上

31、取得的最大的和1、状态的设计、状态的设计 对于本题来说，状态的选定和存储对整个问题的处理起了决定性的作用。我们从（1，1）出发，每走一步作为一个阶段，则可以分成2*n-1个阶段： 第一个阶段，两条路径从（1，1）出发； 第二个阶段，两条路径可达（2，1）和（1，2）； 第三个阶段，两条路径可达的位置集合为（3，1）、（2，2）和（1，3）； 第2*n-1个阶段，两条路径汇聚（n，n）；在第k(1k2*n-1)个阶段，两条路径的终端坐标（x1，y1）（x2，y2）位于对应的右下对角线上。如下图所示：如果我们将两条路径走第i步的所有可能位置定义为当前阶段的状态的话，面对的问题就是如何存储状态了。方

32、格取数问题的状态数目十分庞大，每一个位置是两维的，且又是求两条最佳路径，这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。为此，我们取位置中的x坐标（x1，x2）作状态，其中（1x1k）and（x11n）and（1x2k）and（x21n）直接由x坐标计算对应的y坐标：（y1=k+1-x1）and（y11n）and（y2=k+1-x2）and（y21n 2、状态转移方程、状态转移方程设两条路径在k阶段的状态为（x1，x2）。由（y1=k+1-x1）（y11.n）得出第一条路径的坐标为（x1，y1）；由（y2=k+1-x2）（y21.n）得出第二

33、条路径的坐标为（x2，y2）。假设在k-1阶段，两条路径的状态为（x1，x2）且（x1，x2）位于（x1，x2）状态的左邻或下邻位置。因此我们设两条路径的延伸方向为d1和d2：di=0，表明第i条路径由（xi，yi）向右延伸至（xi，yi）；di=1，表明第i条路径由（xi，yi）向下延伸至（xi，yi）（1i2）。显然（x1= x2）（d1= d2），表明两条路径重合，同时取走了（x1，y1）和（x1，y1）中的数，这种取法当然不可能得到最大数和的。分析两种可能：若x1=x2，则两条路径会合于x1状态，可取走（x1，y1）中的数(如下图)； x1(x2)x1=x2 x2(x1)若x1x2，则

34、在k阶段，第一条路径由x1状态延伸至x1状态，第二条路径由x2状态延伸至x2状态，两条路径可分别取走（x1，y1）和（x2，y2）中的数(如下图)；设 fk，x1，x2在第k阶段，两条路径分别行至x1状态和x2状态的最大数和。显然k=1k=1时，时，f1f1，1 1，1=01=0；k2k2时，时，fkfk，x x1 1，x x2 2=maxfk-1=maxfk-1， x x1 1，x x2 2+(x+(x1 1，y y1 1) )的数字的数字xx1 1=x=x2 2，fk-1fk-1， x x1 1，x x2 2+(x+(x1 1，y y1 1) )的数字的数字+(x+(x2 2，y y2 2

35、) )的数字的数字xx1 1xx2 2 1k21k2* *n-1n-1，x x1 1可达可达x x1 1的状态集合，的状态集合，x x2 2可达可达x x2 2的状态集合，（的状态集合，（x x1 1xx2 2）(d1 1dd2 2) )；上述状态转移方程符合最优子结构和重叠子问题的特性，因此适用于动态程序设计方法求解。由于第k个阶段的状态转移方程仅与第k-1个阶段的状态发生联系，因此不妨设 f0第k-1个阶段的状态转移方程； f1第k个阶段的状态转移方程；初始时，f01，1=0。经过2*n-1个阶段后得出的f0n，n即为问题的解。3、多进程决策的动态程序设计多进程决策的动态程序设计 由于方格

36、取数问题是对两条路径进行最优化决策的，因此称这类动态程序设计为分阶段、多进程的最优化决策过程。设阶段i：准备走第i步（1i2*n-1）；状态（x1，x2）： 第i-1步的状态号（1x1，x2i-1。x1，x21.n）决策（d1，d2）：第一条路径由x1状态出发沿d1方向延伸、第二条路径由x2状态 出发沿d2方向延伸，可使得两条路径的数和最大（0d1，d21。方向0表示右移，方向1表示下移）；fillchar(f0，sizeof(f0)，0)；行走前的状态转移方程初始化f01，10；for i2 to n+n-1 do阶段：准备走第i步 begin fillchar(f1，sizeof(f1)，

37、0)； 走第i步的状态转移方程初始化 for x11 to i-1 do枚举两条路径在第i-1步时的状态x1和x2 for x21 to i-1 do begin 计算y1和y2； if (x1，y1)和(x2，y2)在界内 then for d10 to 1 do 决策：计算两条路径的最佳延伸方向 for d20 to 1 do begin 第1条路径沿d1方向延伸至(x1，y1）； 第2条路径沿d2方向延伸至(x2，y2)； if (x1，y1)和(x2，y2)在界内)(d1d2)(x1x2) 计算第i步的状态转移方程then f1x1，x2maxf0 x1，x2+mapx1，y1 x1=

38、x2，f0 x1，x2+mapx1，y1+mapx2，y2 x1x2 end；for end；for f0f1；记下第i步的状态转移方程end；for输出两条路径取得的最大数和f0n，n动态程序设计方法的优化动态程序设计方法的优化 下面，我们来分析一个具体实例，并给出多种解法。对于这些解法，我们将指出好的算法好在哪里，差一点的算法差在哪里，通过不同算法的比较，让读者更深刻的领会优化动态程序设计方法的基本思维方式是“不做已经做过的工作”。理想收入问题理想收入问题理想收入是指在股票交易中，以1元为本金可能获得的最高收入，并且在理想收入中允许有非整数股票买卖。已知股票在第i天每股价格是Vi元，1im

39、，求m天后的理想收入。 1、解法解法1 1很容易想到用动态程序设计方法解这道题目。因为要使得第i天获得理想收入，则前一次卖出股票的收入必须最高，否则第i天所持的股票数不可能最多。而要使得第i天所持的股票数最多，则必须检查第i-1天、第i-2天、第1天卖出股票的理想收入。理想收入问题具备了最优子结构和无后效性的特征。设 阶段i：将所持的股票全部卖出的日期（1im） 状态j：前一次卖出股票的日期（0ji-1） 决策k：第j天后买入股票的日期（jki-1）fi表示在第i天收盘时能达到的最高收入，则状态转移方为公式1的含义是：在第i天收盘时能达到的最高收入，是将第j天收盘后的收入，全部用于买入第k天的

40、股票，再在第i天将所持的股票全部卖出所得的收入。采用公式1，可以得到算法1，其时间复杂度是W(m3)，空间复杂度是W(m)。算法算法1：f01；V01； 以1元为本金设定f和v的初始值f1.m0；for i1 to m do 阶段：枚举最后卖出全部股票的日期i for j0 to i-1 do 状态：枚举前一次卖出股票的日期状态：枚举前一次卖出股票的日期j for kj to i-1 do 决策：枚举决策：枚举第第j天天第第i-1天间买入股票的日期天间买入股票的日期k fimaxfi，fj/Vk*Vi； 计算状态转移方程计算状态转移方程1010*/ max1)0(VFiVkVjFiFikj，其

41、中：公式 2 2、解法、解法2 2改变状态表示的含义改变状态表示的含义改变动态程序设计中状态表示的含义，是优化动态程序设计的常用方法。例如此题，我们可以采用两种不同的状态表示方法优化算法2-1。方法1：设Pi表示前i天能获得的最多股票数，可列出如下状态转移方程：这是因为前i天所能获得的最多股票数，或者是前i-1天获得的最多股票数，或者是在第j天将前j天所能获得的最多的股票全部卖出，再买入第i天的股票。显然，前i-1天能获得的最多股票数乘以第i天的股价，就是第i天能达到的最大收入。方法2：设Qi表示前i天能达到的最大收入，可列出如下状态转移方程：就是说前i天所能达到的最大收入，或者是前i-1天所

42、能达到的的最大收入，或者是在第j天买入股票，再在第i天卖出，所能获得的最大收入。 上述两种方法的时间复杂度都是W(m2)。 / *,1max2)0(iVjVjPiPiPij：公式*/ ,1max3)0(iVjVjQiQiQij：公式算法1中，采用了二重循环来确定fj/Vk的最大值。但在确定fi-1所能达到最大值的时候，我们实际上已经求出当0jki-1时，fj/Vk所能达到的最大值。如果能充分利用这一信息，就可以更快地确定fi 所能达到的最大值。如下图所示，要确定粗线下部的最大值，只需比较虚线下部的最大值和灰色部分的最大值即可。3 3、解法、解法3 3粗略利用信息粗略利用信息*/ max*/ max11/ ,1max1/ max,1max/ max,/ maxmax/ max/ max)0()0()0() 10() 1,0() 10()0()0(iViMaxFViVkVjFiVkVjFiFi