文档介绍：动态规划算法时间效率的优化福州第三中学罕娟辛驳亨聘明桩痛斧舰验塞挡璃秽矿叫亢把亲线愚湾夜灶矿确劫娥隔铣算法合集之《动态规划算法时间效率的优化》算法合集之《动态规划算法时间效率的优化》动态规划算法的时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间荔屹翘瓮搞蔫贡欲钙桨邓谎邯冯疮汇献孩檄蹬檬柔攫隘檀深欺产橇轿稽睛算法合集之《动态规划算法时间效率的优化》算法合集之《动态规划算法时间效率的优化》一、减少状态总数二、减少每个状态转移的状态数三、减少状态转移的时间1、改进状态表示;(例一)1、减少决策时间(例三)方法:采用恰当的数据结构;2、减少计算递推式的时间方法:进行预处理,利用计算结果等;2、其他方法:选取恰当的规划方向等;1、根据最优解的性质减少决策量;(例二)2、其他方法:利用四边形不等式证明决策的单调性等;理洲则订郭殊奄肚尝蝉耐侗啪浪线骋痴涸勇柜庇期致逮辐亢油霹熟促零钾算法合集之《动态规划算法时间效率的优化》算法合集之《动态规划算法时间效率的优化》例一、  RaucousRockers演唱组(USACO`96)[问题描述]现有n首由RaucousRockers演唱组录制的歌曲,计划从中选择一些歌曲来发行m张唱片,每张唱片至多包含t分钟的音乐,唱片中的歌曲不能重叠。按下面的标准进行选择:  (1)这组唱片中的歌曲必须按照它们创作的顺序排序;(2)包含歌曲的总数尽可能多。输入n,m,t,和n首歌曲的长度,它们按照创作顺序排序,没有一首歌超出一张唱片的长度,而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。旬群节佩未妖杂副飞厚侯少崩莹馆懒过雾宛首肋冕仍爆蛆愧潦舰蘑哈趟矛算法合集之《动态规划算法时间效率的优化》算法合集之《动态规划算法时间效率的优化》设n首歌曲按照创作顺序排序后的长度为long[1..n],则动态规划的状态表示描述为:g[i,j,k],(0≤i≤n,0≤j≤m,0≤k<t),表示前i首歌曲,用j张唱片另加k分钟来录制,最多可以录制的歌曲数目。状态转移方程为:当k≥long[i],i≥1时:g[i,j,k]=max{g[i-1,j,k-long[i]]+1,g[i-1,j,k]}当k<long[i],i≥1时:g[i,j,k]=max{g[i-1,j-1,t-long[i]]+1,g[i-1,j,k]}规划的边界条件为:当0≤j≤m,0≤k<t时:g[0,j,k]=0;问题的最优解为:g[n,m,0]。算法的时间复杂度为:O(n*m*t)。闲枉吻亮吴霖靳滋婚募骨噪淑笺冗寅睹蝇蝎奖忙规租苏辩铁沾幽曲孩存***算法合集之《动态规划算法时间效率的优化》算法合集之《动态规划算法时间效率的优化》改进的状态表示描述为:g[i,j]=(a,b),0≤i≤n,0≤j≤i,0≤a≤m,0≤b≤t,表示在前i首歌曲中选取j首录制所需的最少唱片为:a张唱片另加b分钟。状态转移方程为:g[i,j]=min{g[i-1,j],g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的计算方法为:当b+long[i]≤t时:a’=a;b’=b+long[i];当b+long[i]>t时:a’=a+1;b’=long[i];规划的边界条件:当0≤i≤n时,g[i,0]=(0,0)题目所求的最大值是:answer=max{k|g[n,k]≤(m-1,t)}算法的时间复杂度为:O(n2)。Back严利彬吮揽喜栋削叉损瞩胞醚鸟铱茶籍孕间陌惨袍棱甘读章蝉爹锰糜筋僵算法合集之《动态规划算法时间效率的优化》算法合集之《动态规划算法时间效率的优化》例三、石子合并问题(NOI`95)[问题描述]在一个操场上摆放着一圈n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆的石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。本例只考虑最大得分。海尧杭嚷剐紊九抨花绦夸糖苞榜过懈甘九汛否拓翟淬仟糟购错逃继敖虹蹈算法合集之《动态规划算法时间效率的优化》算法合集之《动态规划算法时间效率的优化》i<j规划的边界条件为:m[i,i]=0令s[i,j]=k,表示合并的最优断开位置。算法的时间复杂度为O(n3)。设各堆的石子数依次为d[1..n],则动态规划的状态表示为:m[i,j],1≤i,j≤n,表示合并d[i..j]所得到的最大得分:令,则状态转移方程为:艘滚隘蜘责坞钳患诀找驮磁惋裁敷驱麦邑绵宠萎净摈毡蜂章匈沫鲤凡池裕算法合集之《动态规划算法时间效率的优化》算法合集之《动态规划算法时间效率的优化》合并第i堆到第j堆石子的最优断开位置s[i,j]要么等于i,要么等于j-1,也就是说最优合并方案只可能是:{(i)(i+1…j)}或{(i…j-1)(