《最新区间类型动态规划PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新区间类型动态规划PPT课件.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、合并类动态规划的特点合并类动态规划的特点 合并：意思就是将两个或多个部分进行整合，当合并：意思就是将两个或多个部分进行整合，当然也可以反过来，也就是是将一个问题进行分解然也可以反过来，也就是是将一个问题进行分解成两个或多个部分。成两个或多个部分。 特征：能将问题分解成为两两合并的形式特征：能将问题分解成为两两合并的形式 求解：对整个问题设最优值，枚举合并点，将问求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分题分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类的最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。似分
2、治算法的解题思想。 典型试题：整数划分，凸多边形划分、石子合并典型试题：整数划分，凸多边形划分、石子合并、多边形合并、能量项链等。、多边形合并、能量项链等。分析 假设只有假设只有2堆石子，显然只有堆石子，显然只有1种合并方案种合并方案 如果有如果有3堆石子，则有堆石子，则有2种合并方案，种合并方案，(1,2),3)和和(1,(2,3) 如果有如果有k堆石子呢？堆石子呢？ 不管怎么合并，总之最后总会归结为不管怎么合并，总之最后总会归结为2堆，如果我们把最堆，如果我们把最后两堆分开，左边和右边无论怎么合并，都必须满足最优后两堆分开，左边和右边无论怎么合并，都必须满足最优合并方案，整个问题才能得到最
3、优解。如下图：合并方案，整个问题才能得到最优解。如下图：动态规划动态规划 设设ti,j表示从第表示从第i堆到第堆到第j堆石子数总和。堆石子数总和。Fmax(i,j)表示将从第表示将从第i堆石子合并到第堆石子合并到第j堆石子的最大的得分堆石子的最大的得分Fmin(i,j)表示将从第表示将从第i堆石子合并到第堆石子合并到第j堆石子的最小的得分堆石子的最小的得分同理，同理， Fmaxi,i = 0，Fmini,i = 0 时间复杂度为时间复杂度为O(n3),), 1max(),max(),max(max1jitjkFkiFjiFjki,), 1min(),min(),min(min1jitjkFki
4、FjiFjki优化 由于石子堆是一个圈，因此我们可以枚举分开的位置，首由于石子堆是一个圈，因此我们可以枚举分开的位置，首先将这个圈转化为链，因此总的时间复杂度为先将这个圈转化为链，因此总的时间复杂度为O(n4)。 这样显然很高，其实我们可以将这条链延长这样显然很高，其实我们可以将这条链延长2倍，扩展成倍，扩展成2n-1堆，其中第堆，其中第1堆与堆与n+1堆完全相同，第堆完全相同，第i堆与堆与n+i堆完全堆完全相同，这样我们只要对这相同，这样我们只要对这2n堆动态规划后，枚举堆动态规划后，枚举f(1,n),f(2,n+1),f(n,2n-1)取最优值即可即可。取最优值即可即可。 时间复杂度为时间
5、复杂度为O(8n3),如下图：如下图：猜想猜想 合并第合并第i堆到第堆到第j堆石子的最优断开位置堆石子的最优断开位置si,j要么等要么等于于i+1，要么等于，要么等于j-1，也就是说最优合并方案只可，也就是说最优合并方案只可能是：能是： (i) (i+1 j) 或者或者 (i j-1) (j) 证明 设合并第设合并第i堆到第堆到第j堆石子的断开位置堆石子的断开位置 p，且，且ipj-1。设在。设在i,p之间存在一种断开方案之间存在一种断开方案q。如下图；。如下图；情况情况1：ti, ptp+1,j 合并方案合并方案1： (iq) (q+1.p) (p+1j) ，它的得分，它的得分 : F1=F
6、max(i, q)+Fmax(q+1,p)+Fmax(p+1,j)+ti, j+ti, p合并方案合并方案2: (iq) (q+1.p) (p+1j) ，它的得分，它的得分： F2 = Fmax i, q+Fmax q+1,p+Fmax p+1,j+ti, j+tq+1,j由于由于qp，所以，所以ti, ptp+1,jtq+1,j，所以，所以F1tp+1,j 与情况与情况1是对称。（证明略）是对称。（证明略）状态转移方程 设设ti,j表示从第表示从第i堆到第堆到第j堆石子数总和。堆石子数总和。Fmax(i,j)表示将从第表示将从第i堆石子合并到第堆石子合并到第j堆石子的最大的得分堆石子的最大的
7、得分Fmin(i,j)表示将从第表示将从第i堆石子合并到第堆石子合并到第j堆石子的最小的得分堆石子的最小的得分同理，同理， Fmaxi,i = 0，Fmini,i = 0 时间复杂度为时间复杂度为O(n2),)1,max(), 1max(),max(maxjitjiFjiFjiF,)1,min(), 1min(),min(minjitjiFjiFjiF能量项链能量项链 在在Mars星球上，每个星球上，每个Mars人都随身佩带着一串能量项链。人都随身佩带着一串能量项链。 在项链上有在项链上有N颗能量珠。颗能量珠。 能量珠是一颗有头标记与尾标记的珠子，这些标记对应着能量珠是一颗有头标记与尾标记的珠
8、子，这些标记对应着某个正整数。某个正整数。 对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。如果前一颗能量珠的头标记为颗珠子的头标记。如果前一颗能量珠的头标记为m，尾标，尾标记为记为r，后一颗能量珠的头标记为，后一颗能量珠的头标记为r，尾标记为，尾标记为n，则聚合后，则聚合后释放的能量为释放的能量为mrn（Mars单位），新产生的珠子的头单位），新产生的珠子的头标记为标记为m，尾标记为，尾标记为n。 显然，对于一串项链不同的聚合顺序得到的总能量是不同显然，对于一串项链不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使
9、一串项链释放出的总能量的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。最大。 分析样例：分析样例：N=4，4颗珠子的头标记与尾标记依次为颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。 我们用记号我们用记号表示两颗珠子的聚合操作，释放总能量：表示两颗珠子的聚合操作，释放总能量：(4 1) 2) 3）=10*2*3+10*3*5+10*5*10=710动态规划 该题与石子合并完全类似。该题与石子合并完全类似。 设链中的第设链中的第i颗珠子头尾标记为颗珠子头尾标记为(Si-1与与Si)。 令令F(i,j)表示从第表示从第i颗珠子一直合并到第颗珠子一直合并到第
10、j颗珠子所能颗珠子所能产生的最大能量，则有：产生的最大能量，则有：F(i,j)=MaxF(i,k)+F(k+1,j)+Si-1*Sk*Sj, i=kj 边界条件：边界条件：F(i,i)=0 1=ikj=n 至于圈的处理，与石子合并方法完全相同，时间至于圈的处理，与石子合并方法完全相同，时间复杂度复杂度O(8n3) 。凸多边形的三角剖分凸多边形的三角剖分 给定由给定由N顶点组成的凸多边形顶点组成的凸多边形 每个顶点具有权值每个顶点具有权值 将凸将凸N边形剖分成边形剖分成N-2个三角形个三角形 求求N-2个三角形顶点权值乘积之和最小？个三角形顶点权值乘积之和最小？ 样例样例上述凸五边形分成上述凸五
11、边形分成123 ， 135， 345三角形顶点权值乘积之和为：三角形顶点权值乘积之和为：121* *122* *123+121* *123* *231+123* *245* *231= 12214884分析性质：一个凸多边形剖分一个三角形后，可以将性质：一个凸多边形剖分一个三角形后，可以将凸多边形剖分成三个部分：凸多边形剖分成三个部分：u一个三角形一个三角形u二个凸多边形（图二个凸多边形（图2可以看成另一个凸多边形可以看成另一个凸多边形为为0）动态规划 如果我们按顺时针将顶点编号，则可以相邻两个顶点描如果我们按顺时针将顶点编号，则可以相邻两个顶点描述一个凸多边形。述一个凸多边形。 设设f(i,
12、j)表示表示ij这一段连续顶点的多边形划分后最小乘积这一段连续顶点的多边形划分后最小乘积 枚举点枚举点k，i、j和和k相连成基本三角形，并把原多边形划分相连成基本三角形，并把原多边形划分成两个子多边形，则有成两个子多边形，则有 f(i,j)=minf(i,k)+f(k,j)+ai*aj*ak 1=ikj=n 时间复杂度时间复杂度O(n3)讨论为什么可以不考虑这种情况？为什么可以不考虑这种情况？ 可以看出图可以看出图1和图和图2是等价的，也就是说如果是等价的，也就是说如果存在图存在图1的剖分方案，则可以转化成图的剖分方案，则可以转化成图2的剖的剖分方案，因此可以不考虑图分方案，因此可以不考虑图1
13、的这种情形。的这种情形。多边形（多边形（IOI98IOI98） 多角形是一个单人玩的游戏，开始时多角形是一个单人玩的游戏，开始时有一个有一个N N个顶点的多边形。如图，这个顶点的多边形。如图，这里里N=4N=4。每个顶点有一个整数标记，。每个顶点有一个整数标记，每条边上有一个每条边上有一个“+ +”号或号或“* *”号。号。边从边从1 1编号到编号到N N。 第一步，一条边被拿走；随后各步包第一步，一条边被拿走；随后各步包括如下：括如下： 选择一条边选择一条边E E和连接着和连接着E E的两个顶点的两个顶点V1V1和和 V2V2； 得到一个新的顶点，标记为得到一个新的顶点，标记为V1V1与与V
14、2V2通通过边过边E E上的运算符运算的结果。上的运算符运算的结果。 最后，游戏中没有边，游戏的得分为最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。仅剩余的一个顶点的值。 -7425+*1234+*样例分析 分析 我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值 。 用f(i,j)表示从点i到点j进行删边操作所能得到的最大值，num(i)表示第i个顶点上的数，若为加法，那么：)(), i (),(),(max),(11inumifkikjfikfjifik进一步分析 最后，我们允许顶点上出现负数。以前的方程还适不适最后，我们允许顶点上出现负数。以前的方程还适不适用呢？用呢
15、？ 这个例子的最优解应该是（这个例子的最优解应该是（3+23+2）* *（-10-10）* *（-5-5）=250=250，然而如果沿用以前的方程，得出的解将是（，然而如果沿用以前的方程，得出的解将是（-10-10）* *3+23+2）* *（-5-5）=125=125。为什么？。为什么？ 我们发现，两个负数的积为正数；这两个负数越小，它我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。大，而从来没有想过负数的积为正数这个问题。 -1032-5*图六+分析分析
16、 对于加法，两个最优相加肯定最优，而对于乘法对于加法，两个最优相加肯定最优，而对于乘法 求最大值：求最大值： 正数正数正数，如果两个都是最大值，则结果最大正数，如果两个都是最大值，则结果最大 正数正数负数，正数最小，负数最大，则结果最大负数，正数最小，负数最大，则结果最大 负数负数负数，如果两个都是最小值，则结果最大负数，如果两个都是最小值，则结果最大 求最小值：求最小值： 正数正数正数，如果两个都是最小值，则结果最小正数，如果两个都是最小值，则结果最小 正数正数负数，正数最大，负数最小，则结果最小负数，正数最大，负数最小，则结果最小 负数负数负数，如果两个都是最大值，则结果最小负数，如果两个
17、都是最大值，则结果最小最终？ 我们引入函数我们引入函数fminfmin和和fmaxfmax来解决这个问题。来解决这个问题。fmax(i,j) fmax(i,j) 表示从点表示从点i i开始，到但开始，到但j j为止进行删为止进行删边操作所能得到的最大值，边操作所能得到的最大值，fmin(i,j) fmin(i,j) 表示最表示最小值。小值。当当OP=OP=+ +Fmax(i,j)=maxfmax(i,k)+fmax(k+1,j)Fmax(i,j)=maxfmax(i,k)+fmax(k+1,j)Fmin(i,j)=minfmin(i,k)+fmin(k+1,j)Fmin(i,j)=minfmi
18、n(i,k)+fmin(k+1,j), 1min(*),(fmin), 1max(*),(fmin), 1min(*),(fmax), 1max(*),(fmax),max(jkfkijkfkijkfkijkfkijif), 1max(*),(fmax), 1max(*),(fmin), 1min(*),(fmax), 1min(*),(fmin),min(jkfkijkfkijkfkijkfkijif当当OP=OP=* *完美解决 初始值初始值 Fmax(i,i)=num(i)Fmax(i,i)=num(i) Fmin(i,i)=num(i) Fmin(i,i)=num(i) 1=i=k=j
19、=n1=i=k=D2,只要证明只要证明d(1,3) +d(2,4)d(1,2)+d(3,4)连接两边，见图连接两边，见图3，由三角形的三边关系定理即可证明。，由三角形的三边关系定理即可证明。分析 结论：青蛙在结论：青蛙在1号结点只能跳到号结点只能跳到2号结点或者号结点或者n号结点。号结点。 如果青蛙跳到了如果青蛙跳到了2号结点，则问题转化为：从号结点，则问题转化为：从2出发，遍历出发，遍历2.n一次一次仅一次的最短距离。仅一次的最短距离。 如果青蛙跳到了如果青蛙跳到了n号结点，则问题转化为：从号结点，则问题转化为：从n出发，遍历出发，遍历2.n一次一次仅一次的最短距离。仅一次的最短距离。 这实
20、际上是递归的思维，把问题转化为了本质相同但规模这实际上是递归的思维，把问题转化为了本质相同但规模更小的子问题更小的子问题,如下图。如下图。动态规划(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)。1,1,) 1 , 1, 11(1,1,)0 , 1, 1(
21、min)0 ,(LsLssdistLsfsssdistLsfLsf跳到跳到2,2, 1) 1 , 1,(,1,)0 , 1,(min) 1 ,(LsLsLsdistLsfsLssdistLsfLsf跳到跳到动态规划(2) F(i,j,0)表示还有表示还有ij号点没访问号点没访问,且青蛙停在且青蛙停在i的最小值的最小值F(i,j,1)表示还有表示还有ij号点没访问号点没访问,且青蛙停在且青蛙停在j的最小值的最小值 状态总数为状态总数为n2，状态转移的复杂度为，状态转移的复杂度为O(1)，总的时间复杂度，总的时间复杂度为为O(n2)。jijidistjifiiiidistjifjif跳到停在跳到停
22、在,) 1 , 1(1,1,)0 , 1(min)0 ,(ijidistjifjjjdistjifjif，跳到停在，跳到停在j,)0 , 1-,(1j,1,) 1 , 1,(min) 1 ,(主程序for i:=1 to n do for j:=n downto i+1 do begin update(fi+1,j,0,fi,j,0+di,i+1); / 停在i,跳到i+1 update(fi+1,j,1,fi,j,0+di,j); / 停在i,跳到j update(fi,j-1,0,fi,j,1+di,j); / 停在j,跳到i update(fi,j-1,1,fi,j,1+dj-1,j);
23、 / 停在j,跳到j-1 end;棋盘分割棋盘分割 将一个将一个的棋盘进行如下分割：将原棋盘割下一块矩的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行每次切割都只能沿着棋盘格子的边进行)允许的分割方案允许的分割方案 不允许的分割方案不允许的分割方案任务：任务：棋盘上每一格有一个分值，一块矩形棋盘的棋盘上每一格有一个分值，一块矩形棋盘的总总分分为
24、其所含各格分值之和。现在需要把棋盘按为其所含各格分值之和。现在需要把棋盘按上述规则分割成上述规则分割成n块矩形棋盘，并使各矩形棋块矩形棋盘，并使各矩形棋盘总分的盘总分的均方差均方差最小。最小。 均方差均方差 ： 算术平均值算术平均值 ：nxxnii21)(nxxnii1样例 输入输入31 1 1 1 1 1 1 31 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3输出输出1.633均方差公式化简均方差公式化简21221221122112
25、22122122112121)2()2()()(xxnxxnxxnxxnxnxxxxnnxxxxnxxnxxniiniiniiniiniiniiniiiniinii分析 由化简后的均方差公式：由化简后的均方差公式： 可知，均方差的平方为每格数的平方和除以可知，均方差的平方为每格数的平方和除以n，然，然后减去平均值的平方，而后者是一个已知数。后减去平均值的平方，而后者是一个已知数。 因此，在棋盘切割的各种方案中，只需使得每个棋因此，在棋盘切割的各种方案中，只需使得每个棋盘内各数值的平方和最小即可。盘内各数值的平方和最小即可。 因此，我们需要求出各棋盘分割后的每个棋盘各数因此，我们需要求出各棋盘分
26、割后的每个棋盘各数平方和的最小值，设为平方和的最小值，设为w，那么，那么 答案为：答案为：21221xxnnii2/xnwans棋盘切割后的四种情况动态规划动态规划 设设F(i,x1,y1,x2,y2)表示以表示以x1,y1x2,y2为四边形对角线为四边形对角线的棋盘切割成的棋盘切割成k块的各块数值总平方和的最小值，块的各块数值总平方和的最小值，则有：则有： 1=X1,x2,x3,x4=8,1=i=n。 设棋盘边长为设棋盘边长为m,则状态数为则状态数为nm4 ,决策数最多决策数最多m。 先预处理从左上角先预处理从左上角(1,1)到右下角到右下角(i,j)的棋盘和时间的棋盘和时间复杂度为复杂度为
27、O(m2)，因此转移为，因此转移为O(1),总时间复杂度为总时间复杂度为O(nm5)。右面不动竖切左面不动竖切下面不动横切上面不动横切, 1), 1(,), 1, 1(,1,), 1(,) 1, 1(min),(2212112112211112112111112211yxybDybyxifybyxDyxybifaxyxDaxyxifaxyxDaxyxifyxyxif总结总结 该类问题的基本特征是能将问题分解成为两两合并的形式该类问题的基本特征是能将问题分解成为两两合并的形式。解决方法是对整个问题设最优值，枚举合并点，将问题。解决方法是对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的最优值进分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似分治的解题思想。行合并得到原问题的最优值。有点类似分治的解题思想。 设前设前i到到j的最优值，枚举剖分（合并）点，将的最优值，枚举剖分（合并）点，将(i,j)分成左右分成左右两区间，分别求左右两边最优值，如下图。两区间，分别求左右两边最优值，如下图。 状态转移方程的一般形式如下：状态转移方程的一般形式如下： F(i,j)=MaxF(i,k)+F(k+1,j)+决策，决策，k为划分点为划分点47 结束语结束语