区间类型动态规划.pptVIP

* * * * * * * * * * * * * * * * * * 完美解决 初始值 Fmax(i,i)=num(i) Fmin(i,i)=num(i) 1=i=k=j=n 空间复杂度:O(n2) 时间复杂度:先要枚举每一条边为O(n)，然后动态规划为O(n3 )，因此总为O(n4)。 青蛙的烦恼 有一个n片荷叶正好在一凸多边形顶点上 有一只小青蛙恰好站在1号荷叶的点 小青蛙可以从一片荷叶上跳到另外任意一片荷叶上 给出N个点的坐标 求小青蛙想通过最短的路程遍历所有的荷叶一次且仅一次的最短路径。 分析一个简单例子 最优遍历方法为：1,2,3,4,5,10,9,8,7,6 (图中红线) D=d(1,5)+d(5,10)+d(6,10) =2*(82+42)1/2+8 =25.889 分析 性质：青蛙遍历的路径不会相交。 上图中图2的路径比图1要短。 证明：图1: D1=d(1,3)+d(2,3)+d(2,4) 图2: D2=d(1,2)+d(2,3)+d(3,4) 要证明D1D2,只要证明d(1,3) +d(2,4)d(1,2)+d(3,4) 连接两边，见图3，由三角形的三边关系定理即可证明。 分析 结论：青蛙在1号结点只能跳到2号结点或者n号结点。 如果青蛙跳到了2号结点，则问题转化为：从2出发，遍历2..n一次仅一次的最短距离。 如果青蛙跳到了n号结点，则问题转化为：从n出发，遍历2..n一次仅一次的最短距离。 这实际上是递归的思维，把问题转化为了本质相同但规模更小的子问题,如下图。 动态规划(1) f(s,L,0)表示从s出发，遍历s..s+L-1一次且仅一次的最短距离; f(s, L,1)表示从s+L-1出发，遍历s..s+L-1一次且仅一次的最短距离。状态转移方程为： 状态总数为n2，状态转移的复杂度为O(1)，总的时间复杂度为O(n2)。 动态规划(2) F(i,j,0)表示还有i~j号点没访问,且青蛙停在i的最小值 F(i,j,1)表示还有i~j号点没访问,且青蛙停在j的最小值 状态总数为n2，状态转移的复杂度为O(1)，总的时间复杂度为O(n2)。 主程序 for i:=1 to n do for j:=n downto i+1 do begin update(f[i+1,j,0],f[i,j,0]+d[i,i+1]); // 停在i,跳到i+1 update(f[i+1,j,1],f[i,j,0]+d[i,j]); // 停在i,跳到j update(f[i,j-1,0],f[i,j,1]+d[i,j]); // 停在j,跳到i update(f[i,j-1,1],f[i,j,1]+d[j-1,j]); // 停在j,跳到j-1 end; 棋盘分割 将一个８×８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行) 允许的分割方案 不允许的分割方案 任务： 棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。 均方差 ： 算术平均值 ： 样例 输入 3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 3 输出 1.633 均方差公式化简 分析 由化简后的均方差公式： 可知，均方差的平方为每格数的平方和除以n，然后减去平均值的平方，而后者是一个已知数。 因此，在棋盘切割的各种方案中，只需使得每个棋盘内各数值的平方和最小即可。 因此，我们需要求出各棋盘分割后的每个棋盘各数平方和的最小值，设为w，那么 答案为： 棋盘切割后的四种情况 动态规划 设F(i,x1,y1,x2,y2)表示以[x1,y1][x2,y2]为四边形对角线的棋盘切割成k块的各块数值总平方和的最小值，则有： 1=X1,x2,x3,x4=8,1=i=n。 设棋盘边长为m,则状态数为nm4 ,决策数最多m。 先预处理从左上角(1,1)到右下角(i,j)的棋盘和时间复杂度为O(m2)，因此转移为O(1),总时间复杂度为O(nm5)。 总结 该类问题的基本特征是能