[noip动态规划1.pptVIP

动态程序设计 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 动态规划 与递归程序相类，将对问题求解分解为对子问题求解；不同之处在于把子问题的解存起来，用空间换时间。 例：Fibonacci数 F(0)=0; F(1)=1; F(n)=F(n-1)+F(n-2); 递归: F(n-1)和F(n-2)分别求到底一次 动态规划：用数组将前n-1个数存起来，每次只用一个加法 F[n] = F[n-1]+F[n-2] 即可。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例１　最短路径问题。下图中给出一个地图，地图中每个顶点代表一个城市，两个城市之间的连线表示道路，连线上的数值代表道路的长度。现在，想从城市A到城市E，怎样走路程最短，最短路程的长度是多少？ 现在，我们想从城市A到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？ 设：Dis[x]为城市x到城市E的最短路径长度（x表示任意一个城市）;Map[i,j]表示i，j两个城市间的距离，若map[i,j]=0，则两个城市不通。 我们可以使用回溯来计算Dis[x]: Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. var s:未访问的城市聚合； function search(who):integer; {求城市Who与城市E的最短距离} Var i,j,min:integer; begin if who=E then search:=0 else begin min:=maxint; for i取遍所有城市 do if (map[who,i]0) and (i in s) then begin s:=s-[i]; {城市i已访问} j:=map[who,i]+search(i); {计算城市E至城市Who的路径长度} s:=s+[i]; {恢复城市i未访问状态} if jmin then min:=j; {若城市E至城市Who的路径长度为目前最短，则记下} end; search:=min; {返回城市E至城市的最短路径长度} end; begin s:=所有城市； dis[a]:=search(a); {计算城市A城市E的最短路径长度} writeln(dist[a]); end. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要，所以时间复杂度为W(n!)，这是一个“指数级”的算法。那么还有没有效率更高的解题方法呢？ 首先，我们来观察上述算法。在求B1到E的最短路径的时候，先求出从C2到E的最短路径；而在求B2到E的最短路径的时候，又求了一遍从C2到E的最短路径。也就是说，从C2到E的最短路径求了两遍。两样可以发现，在求从C1、C2到E的最短路径的过程中，从D1到E的最短路径也被求了两遍。而在整个过程中，从D1到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即由后往前依次推出每个Dis值，直到推出Dis[A]为止。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 阶段的划分具有如下性质： ⑴阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生