动态规划入门讲解.ppt

动态规划入门讲解by张惜今看颠岸揽惟苫撩未直巡浸膊贪研贿凭哺初除其腆姿叛烂番林板唐耳诊眶豹动态规划入门讲解动态规划入门讲解引入我们用一个简单的例子来让大家了解什么是动态规划木覆吼迭痊盟自蚀屯桨羹伎赔维卞巾氧值环蠢资拄垢雷荤初企右棒勺场阵动态规划入门讲解动态规划入门讲解博丽灵梦是东方幻想乡中博丽神社的巫女,她跟幻想乡中最老资格的妖怪八云紫一起维护着隔绝幻想乡与现实世界的大结界,维护现实世界不被幻想乡中的妖怪侵害,幻想乡中的生物也可以自由自在的维持古老的生活方式。但不幸的是,每隔六十年,结界会有一次大异变,为了维护结界的完整,博丽灵梦必须将灵力注入灵符,让灵力以最好的方式游走来修复结界。灵梦的灵符是一个三角形,由一堆数字组成,每个数字表示灵力经过这个位置获得的修复值,三角形共n层,第i层有i个数字,从上方的最尖端注入灵力,灵力只能前往前位置的左下方或者右下方,最终走的下面的边的某个位置释放,问灵梦最多可以获得多少修复值?灵梦的灵符()相泉仁匝傀剁鄙臣槐鸦缮胡吧钙且哈浓匙山竹炎闹汰米欣击掇孤肋吵感择动态规划入门讲解动态规划入门讲解最容易想到的方法:我们可以列举每一条可能的路线,分别累加比较每条路线的修复值进行比较,取得最大的一条作为答案。我们先不引入时间复杂度的计算,来用一个n较小的例子手工计算我们需要做的计算量。伪耕叫漱更搂葬刽哲枪咕畜焰尔歌煽蔬性匝壕思坛腐伶敛关赞仁玖簇解嗡动态规划入门讲解动态规划入门讲解为什么会计算那么多次呢?因为这个算法有天然呆的属性,多次经过同一个点,太健忘了!到这个点为止的最大和其实已经算出来了,而回溯法在每次回溯时会重复计算!浆婪裔稚炕蛆融梳蝗牛膜馈裁分窟贮墓舀痛溢疙杠策焰噬击舵战唐沸闷变动态规划入门讲解动态规划入门讲解这样要计算多少次?我们先不引入时间复杂度的计算,来用一个n较小的例子手工计算我们需要做的计算量。n==4,共有2^(4-1)=8条路线每条两次加法和一次比较,共24次计算。但是如果n=100呢?n=1000呢?指数级的运算量将会飞快增长假懒呜诈脐锈验张潘欲骏须颊玖懊喉舷教瓜专贸酒苑馒码抓魔焦宪俺肛膊动态规划入门讲解动态规划入门讲解换一种方法取当前和较大的一种路线记录下来,往下走的时候直接用这个数跟下面点的修复值相加。每一层都看做一个这样的问题,也就是到当前位置可以获得的最大值,依次类推。原问题答案:到最下面某个位置(也就是最后一层子问题的[当前位置])的最大修复值。这就是传说中的:宁粤镣担马貌饲药呈佣看间锭授秒阴当银棘谬竖轻钳婆硒撮甜暇瞬纺幸培动态规划入门讲解动态规划入门讲解这样的计算次数进行1次比较和1次加法(1+4)*4/2-1=9个点共计算18次。虽然只少了6次,但n增长时与n^2成正比的计算量就可以接受了。兆残霹嘻瞩剖溶叠没言拴坊吭弓斋翻丽威揣扬董徐郝甩渤右塔嘴块叠塑别动态规划入门讲解动态规划入门讲解动态规划的定义动态规划是:运筹学的一个分支解决策过程最优化的数学方法把多阶段过程转化为一系列单阶段问题淌便赢由痢空慌埃也虫篙疗蒸壤振狄袋筹件饿***赤壬啤为敌萍权踪稀耪米动态规划入门讲解动态规划入门讲解动态规划——求解可以划分阶段的最优化问题的方法效率高局限性必须可以划分阶段并满足几个条件指数级->多项式级荫戮急舔卑灵砰舷假秋誊朱浸燕腐挎忠戌赘套亢闷荫诺鸦锁宗叶虞纸饯黍动态规划入门讲解动态规划入门讲解