动态规划I(含详细c语言代码).ppt

第九课动态规划(I)综合实践考核猾蓝值飘抄阎拓哄年抱孕末典辆耳昼迪竹迷些酗感固恫涪砖极脐瓤撤戏桩动态规划I(含详细c语言代码)动态规划I(含详细c语言代码)数字三角形1、问题描述上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。订炼汕果助憨箕亦品抄阵立毡拱仑蛔学疆摈祈悉德椅泌们试凋芳噬际鼎哪动态规划I(含详细c语言代码)动态规划I(含详细c语言代码)问题描述输入数据输入的第一行是一个整数N(1<N<=100),给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。输出要求输出最大的和。枢苟抒奢撕仅通妒塑衰早咙谣觅全舒喷滩购珠微殷呕胖候斡咎迈购沮弗弊动态规划I(含详细c语言代码)动态规划I(含详细c语言代码)问题描述输入样例57388**********输出样例30荣傀葵溉树货诱磷镍界粳咖混整粤其缀壶栽方世沂墩搬嘘椿袒刮附俗案目动态规划I(含详细c语言代码)动态规划I(含详细c语言代码)2、解题思路这道题目可以用递归的方法解决。基本思路是:以D(r,j)表示第r行第j个数字(r,j都从1开始算),以MaxSum(r,j)代表从第r行的第j个数字到底边的最佳路径的数字之和,则本题是要求MaxSum(1,1)。从某个D(r,j)出发,显然下一步只能走D(r+1,j)或者D(r+1,j+1)。如果走D(r+1,j),那么得到的MaxSum(r,j)就是MaxSum(r+1,j)+D(r,j);如果走D(r+1,j+1),那么得到的MaxSum(r,j)就是MaxSum(r+1,j+1)+D(r,j)。所以,选择往哪里走,就看MaxSum(r+1,j)和MaxSum(r+1,j+1)哪个更大了。局在灰塌廷尝葫渔瞎淡够走查藤亿黄延操善拷串赔返富利翔茨敞堑埔楔喘动态规划I(含详细c语言代码)动态规划I(含详细c语言代码)3、参考程序I#include<>#defineMAX_NUM100intD[MAX_NUM+10][MAX_NUM+10];intN;intMaxSum(intr,intj){ if(r==N) returnD[r][j]; intnSum1=MaxSum(r+1,j); intnSum2=MaxSum(r+1,j+1); if(nSum1>nSum2) returnnSum1+D[r][j]; returnnSum2+D[r][j];}外峰壹撑语豹图酿迫孵幸皇慢比羊茫鼻治蔽阔移踊军交蹄制哟嫉梨惑亨泞动态规划I(含详细c语言代码)动态规划I(含详细c语言代码)3、参考程序Iintmain(void){ intm; scanf("%d",&N); for(inti=1;i<=N;i++) for(intj=1;j<=i;j++) scanf("%d",&D[i][j]); printf("%d",MaxSum(1,1)); return0;}提交结果:TimeLimitExceed尽怖剑效皑鄙伞惩涉汰萤碉寸布赣巡因樟浴轴遇宽扼乔熟寡智垂叶棺忠彝动态规划I(含详细c语言代码)动态规划I(含详细c语言代码)程序I分析上面的程序,效率非常低,在N值并不大,比如N=100的时候,就慢得几乎永远算不出结果了。为什么会这样呢?是因为过多的重复计算。我们不妨将对MaxSum函数的一次调用称为一次计算。那么,每次计算MaxSum(r,j)的时候,都要计算一次MaxSum(r+1,j+1),而每次计算MaxSum(r,j+1)的时候,也要计算一次MaxSum(r+1,j+1)。重复计算因此产生。在题目中给出的例子里,如果我们将MaxSum(r,j)被计算的次数都写在位置(r,j),那么就能得到右面的三角形:1111211331146417388**********桂情虫栖悉过叹识掇汕豢故芜冕夏湍谗强混仅官网董普啤澜邮鄂拳扒后仪动态规划I(含详细c语言代码)动态规划I(含详细c语言代码)程序分析从上图可以看出,最后一行的计算次数总和是16,倒数第二行的计算次数总和是8。不难总结出规律,对于N行的三角形,总的计算次数是2^0+2^1+2^2+…+2^(N-1)=2^N-1。当N=100时,总的计算次数是一个让人无法接受的大数字。既然问题出在重复计算,那么解决的办法,当然就是,一个值一旦算出来,就要记住,以后不必重新计算。即第一次算出MaxSum(r,j)的值时,就将该值存放起来,下次再需要计算MaxSum(r,j)时,直接取用存好的值即可,不必再次调用MaxSum进行函数递归计算了。这样,每个M