动态规划入门讲解教案.ppt

《动态规划入门讲解教案.ppt》由会员分享，可在线阅读，更多相关《动态规划入门讲解教案.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划入门讲解 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望引入我们用一个简单的例子来让大家了解什么是动态规划 博丽灵梦是东方幻想乡中博丽神社的巫女，她跟幻想乡中最老资格的妖怪八云紫一起维护着隔绝幻想乡与现实世界的大结界，维护现实世界不被幻想乡中的妖怪侵害，幻想乡中的生物也可以自由自在的维持古老的生活方式。但不幸的是，每隔六十年，结界会有一次大异变，为了维护结界的完整，博丽灵梦必须将灵力注入灵符，让灵力以最好的方式游走来修复结界。灵梦的灵符是一个三角形，由一堆

2、数字组成，每个数字表示灵力经过这个位置获得的修复值，三角形共n层，第i层有i个数字，从上方的最尖端注入灵力，灵力只能前往前位置的左下方或者右下方，最终走的下面的边的某个位置释放，问灵梦最多可以获得多少修复值？灵梦的灵符（灵梦的灵符（USACO 1.5.1）最容易想到的方法：我们可以列举每一条可能的路线，分别累加比较每条路线的修复值进行比较，取得最大的一条作为答案。我们先不引入时间复杂度的计算，来用一个n较小的例子手工计算我们需要做的计算量。为什么会计算那么多次呢？因为这个算法有天然呆天然呆的属性，多次经过同一个点，太健忘了！到这个点为止的最大和其实已经算出来了，而回溯法在每次回溯时会重复计算！

3、这样要计算多少次？我们先不引入时间复杂度的计算，来用一个n较小的例子手工计算我们需要做的计算量。n4，共有2(4-1)8条路线 每条两次加法和一次比较，共24次计算。但是如果n=100呢？n=1000呢？指数级的运算量将会飞快增长 无法接受无法接受换一种方法 取当前和较大的一种路线记录下来，往下走的时候直接用这个数跟下面点的修复值相加。每一层都看做一个这样的问题，也就是到当前位置可以获得的最大值，依次类推。原问题答案：到最下面某个位置（也就是最后一层子问题的当前位置）的最大修复值。这就是传说中的：这样的计算次数 进行1次比较和1次加法 （1+4）*4/2-1=9个点 共计算18次。虽然只少了6

4、次，但n增长时与n2成正比的计算量就可以接受了。动态规划的定定义义动态规划是：运筹学的一个分支解决策过程最优化的数学方法把多阶段过程转化为一系列单阶段问题动态规划求解可以划分求解可以划分阶阶段的最段的最优优化化问题问题的方法的方法效率高局限性必须可以划分阶段并满足几个条件指数级-多项式级 动态规划的适用条件适用条件不是一个纯理论的知识看出来这个题题是考用动态规划求解感性的认识1.最最优优子子结结构构当前取得了最优值,那么直接用这个值来参与计算后面的状态能使后面的也最优只要比较取一个值最优的保存2.无后效性无后效性当前作出决策只会影响后面的状态前面的决策的影响都在状态中被包含了顺序 3.重叠子重

5、叠子问题问题也就是有前所述的那种重复计算的减少,动态规划才能减少算法的运行时间动态规划的要素要素阶段状态决策阶阶段段每个状态属于一个阶段有了前后关系保证最优子结构和无后效性比较明显,是前提也是一种特征比如：时间的前后，灵梦的灵符那种层次关系状状态态动态规划时操作的对象表示我们解到了哪一个子问题1维或者多维所属的阶段，一些相关信息决策决策是前面阶段的状态向后面的状态转移的操作是决策把各个阶段的状态依次求出动态规划的求解模式求解模式和程序程序实现实现划分阶段 设计状态 确定决策写出转移 写出方程和边界 递递推：看作推：看作递递推方程，用循推方程，用循环环依次依次递递推出每一个状推出每一个状态态 记

6、忆记忆化搜索：按搜索的方式写，但是化搜索：按搜索的方式写，但是对对于已于已经经搜索搜索过过的的状状态态直接返回最直接返回最优值优值，不再次搜索，不再次搜索按照方程的形态大致分类的几个例题线性选择背包问题区间DPTreeDP空的裂解原子核（空的裂解原子核（POJ1887）灵乌路空有着特别姿态的鸦。左足是“分解之足”、右足是“融合之足”、还有制御两者的右手“第三足”，她以这三足操控著究极的能源。空居住在地灵殿在无聊的时候经常控制原子核进行核裂解来练习自己的能力。她捕捉到了N个原子核，控制每个原子核进行裂解会获得Ci的能量值，她可以依次挑选一个序列进行裂变（不必连续）。但是由于她能力的特殊性，她用来

7、裂解的原子核的能量只能越来越低，否则会导致控制失败而造成核反应制御不能的后果。但是空是一个低智力的笨蛋，她想让你帮忙计算她最多可以控制几个原子核进行裂变。分析分析经典的LIS模型，也就是线性选择型的DP阶段：按顺序处理到哪一个原子核状态:fi表示处理到第i个，且选取第i个的最大序列长度决策：上一个原子核是哪一个（逆推）方程fi=max(fj)+1 1=ji f1=1帕秋莉的帕秋莉的图书图书（POJ3624）帕秋莉诺蕾姬是幻想乡中红魔馆的图书馆管理员，管理着图书馆中10万本魔法书。她总是试图整理这些图书，把质量好的放在一个专门的书架上。这个专用书架承受的最大重量是M，总共有N本候选图书，编号1n

8、，每本有一个重量和知识值Wi和Ki，她想知道，在书架不会超过承重的情况下，图书的知识值最大。分析分析阶段：物品随意排列，以做决定到了哪个物品作为阶段状态：fij表示处理到第i个物品，已经使用重量j得到的最大知识值决策与转移：决策就是对每个物品是否取用，分别转移，取较大的。方程：fij=max(fi-1j,fi-1j-Wi+Ki)1=i=n 0=j=M 后面部分要求Wi=j f0=0萃香的的西瓜萃香的的西瓜伊吹萃香是被赶到幻想乡的鬼，位列鬼族四天王之一，据传为“怪力乱神”四天王中怪的代表。虽然看上去是一个少女，但其实已活了几百年。她有操纵密和疏的能力，可以任意合并和分解周围的东西。幻想乡的夏天的

9、一天，萃香得到了N堆西瓜，她想把这些西瓜合并成一堆，每次只能合并相邻的两堆，合并的代价为这两堆西瓜的数量之和，合并后与这两堆西瓜相邻的西瓜将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，找出一种合理的方法，使总的代价最小。分析分析阶段：顺序排列的西瓜堆将随着合并逐渐减少从i到j的长为j-i+1的区间可以认为是阶段状态：fij表示从i到j合并完成后的最小代价决策和转移：决策就是应该从区间选哪个点分别合并两边（也就是最后一次合并的位置），从i到J-1选一个位置分开合并方程：fij=min(fik+fk+1j+sum(i,k)+sum(k+1,j)i=kj fii=0美美铃铃的看守方案

10、的看守方案(POJ1463)红美铃是一个来自中国的妖精，因为她会一些中国功夫，所以被红魔馆招募做看门人。红魔馆从外面看上去并不是很大，但是由女仆长咲夜控制时间和空间造成的混乱，馆里面空间很大不容易看守。红魔馆内部的建筑房间和道路可以简化成一棵无根树，也就是有N个房间，N-1条路连接这N个房间，并且没有环路。如果美铃在一个房间设置一个监控点，它就可以看守住与这个房间相邻的所有路，她想知道最少设置多少个看守点就能看住所有路。分析分析状态：ft0.1表示对于t号节点,0表示在这个点上设置,看住子树的最数,1表示不在这个点设置,看着子树的最小数决策：设置在这个点或不设置在这个点。如果设置，对子节点设置或不设置取较小的来求和，最后再1，如果不设置，则对子节点设置来求和（原因）方程:ft0=sum(min(fj1,fj0)+1 ft1=sum(fj0)j是t的子节点 如果i是叶子节点：fi0=1 fi1=0其他：可行性 计数 自动机上的DP 贪心DP 集合DP 多进程DP好题推荐：CDOJ1503 USACO2.3.4POJ3691CDOJ1510 小小结结动态规划一般是想起来不容易写起来简单需要很多题目的练习来找到感觉动态规划是很优美的YM各位神犇各位神犇谢谢谢谢！