动态规划入门讲解课件.ppt

动态规划入门讲解;引入; 博丽灵梦是东方幻想乡中博丽神社的巫女，她跟幻想乡中最老资格的妖怪八云紫一起维护着隔绝幻想乡与现实世界的大结界，维护现实世界不被幻想乡中的妖怪侵害，幻想乡中的生物也可以自由自在的维持古老的生活方式。 但不幸的是，每隔六十年，结界会有一次大异变，为了维护结界的完整，博丽灵梦必须将灵力注入灵符，让灵力以最好的方式游走来修复结界。 灵梦的灵符是一个三角形，由一堆数字组成，每个数字表示灵力经过这个位置获得的修复值，三角形共n层，第i层有i个数字，从上方的最尖端注入灵力，灵力只能前往前位置的左下方或者右下方，最终走的下面的边的某个位置释放，问灵梦最多可以获得多少修复值？ ; 最容易想到的方法：;为什么会计算那么多次呢？;这样要计算多少次？;换一种方法; 这样的计算次数; 动态规划的定义;动态规划——求解可以划分阶段的最优化问题的方法; 动态规划的适用条件;1.最优子结构;2.无后效性; 3.重叠子问题;动态规划的要素;阶段;状态;决策;动态规划的求解模式和程序实现;按照方程的形态大致分类的几个例题;空的裂解原子核（POJ1887）;分析;帕秋莉的图书（POJ3624）;分析;萃香的的西瓜;分析;美铃的看守方案(POJ1463);分析;其他：;小结;YM各位神犇