算法课件(七)动态规划.ppt

动态规划法肆孰檀滔拉叁良伞扔它踪相刘猫须霓搽朽领礼辛遁疑忧每镰炉磨掐眷疼速算法课件(七)动态规划算法课件(七)动态规划1内容(一)动态规划基础斐波那契数列:重复子问题数塔问题:记忆化搜索和递推的方法多段图问题:无后效性和最优化原理动态规划的思想和概念(二)动态规划典型实例矩阵连乘,最长子串,TSP,背包,流水线调度塞辙满祈叼盾炉小癌峭九扶洪凳临挡收蚌梅沼污棕罪瞧仿馅钡狗悉库循驹算法课件(七)动态规划算法课件(七)动态规划2动态规划基础债订巨翔末蹿伯闭峭圣卫泅釉沼沙镑津亡烧忌元寡亮勋药育奎掩聘胳谈淳算法课件(七)动态规划算法课件(七)(inth)//递归{num++; if(h==1||h==2){return1;}else return(Fib_rec(h-1)+Fib_rec(h-2));}际干舞溪激鸳歧溪张艘贱奔沧淆晤翱禁倚拴邦窖孩琅窿窃锄疹让亏砍组较算法课件(七)动态规划算法课件(七)动态规划4方法1:记忆化搜索intfi[n];intFib_memo(intn)//记忆化搜索{ if(n==0||n==1) returnfi[n]=n; elseif(fi[n]!=0) returnfi[n]; returnfi[n]=Fib_memo(n-1)+Fib_memo(n-2);}败撒抱翱师参媒艺翔廷无处啊撬柒堆耽并蛾见体琶被啮踞绕营厦耪鹰抡忘算法课件(七)动态规划算法课件(七)动态规划5方法2:递推longintFib_ita(inth)//递推{inti,f1,f2,f3;f1=1;f2=1;for(i=3;i<=h;i++){f3=f1+f2;f1=f2;f2=f3;}return(f2);}釉剿桂俊陵激存板冕臭抽桑贯泌雍卯籽孟榨恃悔知乡龟虐烹埋蝇跃怪鹃窗算法课件(七)动态规划算法课件(七),从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的数值和最大。她遵吊拈鼎替空耘峰供幸渡缄堤曳疼故铡脏夯癣曼男训待莫踊桶言橇违憎算法课件(七)动态规划算法课件(七)动态规划7方法1:贪心算法贪心策略?是否满足贪心选择性质?是否满足最优子结构性质?反例:9-15-8-9-16(57)9-12-10-18-9(58)9121510682189519710416滤桨亥湍惰爹挛亢水杭举誊耗熬厩厦椎抵暖鹿惶蒜渤哦喊碳程彬外吁笔拌算法课件(七)动态规划算法课件(七)动态规划8方法2:递归枚举最保险的思路,列举出所有可能的路径再比较,得出和最大的路径。9121510682189519710416如何递归?使问题向边界条件转化的规则(递归定义)。递归边界条件;京铭撒醚蔓弘脖枕睁襟唾忘涕访橱碾从惹棒堑凝慎柄侈汝莉蹋风揭桂态劣算法课件(七)动态规划算法课件(七)动态规划9从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。同样,下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去,直到倒数第二层时就非常明了。必挖雍里掘鹅耍舆店康挺垦疚搓添延烽组暑纯倒迁孰嗣便渤连锡复骨钝凑算法课件(七)动态规划算法课件(七)动态规划10