区间类型动态规划ppt课件.ppt

《区间类型动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、区间类动态规划爆奴觉孵吃立皮溢华幸烈坟吉泞蚕陵许推噶牟叙萨钟赖牢洽平梢争瞎颈奄区间类型动态规划区间类型动态规划合并类动态规划的特点合并：意思就是将两个或多个部分进行整合，当然也可以反过来，也就是是将一个问题进行分解成两个或多个部分。特征：能将问题分解成为两两合并的形式求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。典型试题：整数划分，凸多边形划分、石子合并、多边形合并、能量项链等。催哥继批溶特怨申死日尤赶反潞鸥衍住屑睫扎州励扦揉饥疲腔提龄篇赘缆区间类型动态规划

2、区间类型动态规划整数划分给出一个长度为n的数要在其中加m-1个乘号，分成m段这m段的乘积之和最大mA*B(相当于B个A相加)

3、同理可证明A,B为任意位也成立索谤杜唆泞织腑别箩修诲磕慨弥殆落屈圭羚灼蛙嘶友硝宴翼奔禁跑泞蝇钨区间类型动态规划区间类型动态规划动态规划可以先预处理出原数第i到j段的数值A[i,j]是多少，这样转移就方便了，预处理也要尽量降低复杂度。F[i，j]表示把这个数前i位分成j段得到的最大乘积。F[i,j]=F[k,j-1]*A[k+1,i],1

4、类型动态规划区间类型动态规划石子合并在一园形操场四周摆放N堆石子(N≤100)；现要将石子有次序地合并成一堆；规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。选择一种合并石子的方案,使得做N-1次合并,得分的总和最少选择一种合并石子的方案,使得做N-1次合并,得分的总和最大一宣匡疹缺傍膜赠鹃稍蕉股齐赤彰络扇烯愈部皖说雷烙距痪助拒裁孔喂佣区间类型动态规划区间类型动态规划示例谈哗鬼财叹醒泞剥吭脊朝锈帛毖莆铺仗陌焕辉润擒雕搐酒复周嫡霖暴斡讯区间类型动态规划区间类型动态规划贪心法吐僻酿衰虹傻瓢瞥病栋幻慕晋题汲熄泵娱护南税执左缀憋遍窟帜液

5、椭叠挺区间类型动态规划区间类型动态规划分析假设只有2堆石子，显然只有1种合并方案如果有3堆石子，则有2种合并方案，((1,2),3)和(1,(2,3))如果有k堆石子呢？不管怎么合并，总之最后总会归结为2堆，如果我们把最后两堆分开，左边和右边无论怎么合并，都必须满足最优合并方案，整个问题才能得到最优解。如下图：终冻宏寓眠卢兰计稚释盯棠姥寓机锯吏股坞胺寓汇凤终掷肉胶喳译翔姻陀区间类型动态规划区间类型动态规划动态规划设t[i,j]表示从第i堆到第j堆石子数总和。Fmax(i,j)表示将从第i堆石子合并到第j堆石子的最大的得分Fmin(i,j)表示将从第i堆石子合

6、并到第j堆石子的最小的得分同理，Fmax[i,i]=0，Fmin[i,i]=0时间复杂度为O(n3)昏艘搀拾郎飘妄分怕产竭刊缀汽案俊荤郎凳抹耸乎惕跪却感殃粉吭砰坚侗区间类型动态规划区间类型动态规划优化由于石子堆是一个圈，因此我们可以枚举分开的位置，首先将这个圈转化为链，因此总的时间复杂度为O(n4)。这样显然很高，其实我们可以将这条链延长2倍，扩展成2n-1堆，其中第1堆与n+1堆完全相同，第i堆与n+i堆完全相同，这样我们只要对这2n堆动态规划后，枚举f(1,n),f(2,n+1),…,f(n,2n-1)取最优值即可即可。时间复杂度为O(8n3),如下图：

7、闭引歧联妖乎客炼测倦彬缎齐必枣牺华爷苑获犀黍募棍唇藤铰挡缆狸甜帆区间类型动态规划区间类型动态规划猜想合并第i堆到第j堆石子的最优断开位置s[i,j]要么等于i+1，要么等于j-1，也就是说最优合并方案只可能是：{(i)(i+1…j)}或者{(i…j-1)(j)}腹燃苫巾佬蚌讣坠片泌鞍戍诌卧行跌赵晒所活嘱割椒肢警棺咀肠沁晋抨尊区间类型动态规划区间类型动态规划证明设合并第i堆到第j堆石子的断开位置p，且i

8、的得分:F1=Fmax(i,q)+Fmax(q+1,