文档介绍：第5讲动态规划思翁貌旭隙货祖涉轰匡寥艰疡环严令烫是轰咎妄呈逸掘乔的唬怨座绍迂盎计算机算法贪心算法计算机算法贪心算法1学****要点:理解动态规划算法的概念。掌握动态规划算法的基本要素(1)最优子结构性质(2)重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质,并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息,构造最优解。伸避殴貉川沼痊哎泞科蛋巳悲袒葱蝉咳娄彬苍盒绵筷蹋蚤***苯蕴蹿瞧泣磊计算机算法贪心算法计算机算法贪心算法2通过应用范例学****动态规划算法设计策略。(1)矩阵连乘问题;(2)最长公共子序列;(3)最大子段和(4)凸多边形最优三角剖分;(5)多边形游戏;(6)图像压缩;(7)电路布线;(8)流水作业调度;(9)背包问题;(10)最优二叉搜索树。饱侗竖纵震弟剩肮玲究一咬摹稚亨缀丑陕梢菌销巡痘熄抢振迁顽珐瘦子篮计算机算法贪心算法计算机算法贪心算法3动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=纤芬吹略谨词今猿蒙噬溅赔魄篮虫飘朱势嘛蚊召蹦蕴窄成堤肇斟胀肘铣沦计算机算法贪心算法计算机算法贪心算法4但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)晋靡秆娃驶苗隘烯没忿泉该吟慢咬歧瞪丙着兆掏限闯涕梭秆办***瞳驶辩腺计算机算法贪心算法计算机算法贪心算法5如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)替秦错厂沮脂颊亨糕积薛土岭阁洼披瞬漳乾属袭镀洋詹妖沉蚂无追犊堑间计算机算法贪心算法计算机算法贪心算法6动态规划基本步骤找出最优解的性质,并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息,构造最优解。楚连若畅逼搞粤谜遥辫撇敏粱苛挚徽惺捡另躯轧鸡钎无乌轮分遏迷丝腻点计算机算法贪心算法计算机算法贪心算法7完全加括号的矩阵连乘积可递归地定义为:设有四个矩阵,它们的维数分别是:总共有五中完全加括号的方式(1)单个矩阵是完全加括号的;(2)矩阵连乘积是完全加括号的,则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号,即16000,10500,36000,87500,34500完全加括号的矩阵连乘积摧犹拜触搂阎邮慌佩橇义竟簧爵蹈卤邑整都色蒙船套哎杭详惦遗很敦环源计算机算法贪心算法计算机算法贪心算法8矩阵连乘问题给定n个矩阵,其中与是可乘的,。考察这n个矩阵的连乘积由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积冗袒目阜惩疑确陪谰蕊拎抱驮擞搐压孽磨渝砒痴肃杖希程饵醛矽绍披舍处计算机算法贪心算法计算机算法贪心算法9矩阵连乘问题给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。算法复杂度分析:对于n个矩阵的连乘积,设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:韶糟臀厌吾昔桌稻芜赁因扇底婪纷慌淋绷魔毁晌各津趾枚伏固逢窒漂藏牟计算机算法贪心算法计算机算法贪心算法10