文档介绍：1本讲纲要⊕-,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的数值和最大。9121510682189519710416问题分析数组存放下三角数据9121510682189519710416口算结果?9->12->10->18->1031贪婪算法贪婪策略?9121510682189519710416是否满足贪婪选择性质?是否满足最优子结构性质?42枚举最保险的思路,列举出所有可能的路径再比较,得出和最大的路径。9121510682189519710416重复工作:循环、递归。如何循环?递归如何?使问题向边界条件转化的规则(递归定义)。递归边界条件;52枚举-[100][100];//下三角形存放数据intmax(inti,intj,intn)//递归函数{intleft,right;if((i==n)||(j==n))//到达边缘returna[i][j];left=max(i+1,j,n);//左边right=max(i+1,j+1,n);//右边return(left>right)?(left+a[i][j]):(right+a[i][j]);}max(1,1,n)max(2,1,n)max(2,2,n)max(3,1,n)max(3,2,n)………………9121510682189519710416重叠子问题:计算了两次18的最大路径。63动态规划的手工计算912 1510 6 82 18 9 519 7 10 4 16阶段5阶段4阶段3阶段2(21)(28)(19)(21)(38)(34)(29)(50)(49)(59)决策决策决策决策阶段15950493834292128192119710416取第i行第j个数,一般有两种方案。73动态规划的手工计算912 1510 6 82 18 9 519 7 10 4 16(33)(49)(41)(37)(31)(30)(32)(21)(24)(52)(56)(59)(45)(53)决策决策决策决策阶段1阶段2阶段3阶段4阶段583动态规划的手工计算顺序与逆序解法本质上无区别;一般当初始状态唯一给定时可用逆序解法;如需比较到达不同终点状态的各个路径及最大结果时,使用顺序法比较简便;如需知道塔中每一点到最下层的最大值和路径时,使用逆序法比较简便。94动态规划的算法实现原始信息存储层数用整型变量n存储;数塔中的数据用二维数组data[][]存储,下三角阵。动态规划过程存储必须用二维数组d[][]存储各阶段的决策结果。二维数组d的存储内容如下:d[n][j]=data[n][j],其中j=1,2,……,n;d[i][j]=max(d[i+1][j],d[i+1][j+1])+data[i][j],其中i=n-1,n-2,……1,j=1,2,……,i;逆序法5950493834292128192119710416最后d[1][1]存储的就是问题的最大值。可以通过分析d,得到路径。104动态规划的算法实现输出data[1][1]“9”;b=d[1][1]-data[1][1]=59-9=50b与d[2][1],d[2][2]比较b与d[2][1]相等,输出data[2][1]“12”;b=d[2][1]-data[2][1]=50-12=38b与d[3][1],d[3][2]比较b与d[3][1]相等,输出data[3][1]“10”;b=a[3][1]-data[3][1]=38-10=28b与d[4][1],d[4][2]比较b与d[4][2]相等,输出data[4][2]“18”;b=d[4][2]-data[4][2]=28-18=10b与d[5][2],d[5][3]比较b与d[5][3]相等,输出data[5][3]“10”。数组d5950493834292128192119710416数组data9121510682189519710416