1、动态规划算法时间效率的优化福州第三中学 毛子青动态规划算法的时间复杂度 =状态总数 *每个状态转移的状态数 *每次状态转移的时间一、减少状态总数二、减少每个状态转移的状态数三、减少状态转移的时间1、改进状态表示； （例一）1、减少决策时间 （例三） 方法：采用恰当的数据结构；2、减少计算递推式的时间方法：进行预处理，利用计算结果等；2、其他方法：选取恰当的规划方向等；1、根据最优解的性质减少决策量； （例二）2、其他方法：利用四边形不等式证明决策的单调性等；例一、 Raucous Rockers 演唱组（ USACO96）问题描述 现有 n首由 Raucous Rockers 演唱组录制的歌曲
2、，计划从中选择一些歌曲来发行 m张唱片，每张唱片至多包含 t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：(1) 这组唱片中的歌曲必须按照它们创作的顺序排序；(2) 包含歌曲的总数尽可能多。输入 n， m， t， 和 n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。设 n首歌曲按照创作顺序排序后的长度为 long1.n， 则动态规划的状态表示描述为：gi, j, k， (0in， 0jm， 0ktp+1,j 与情况 1是对称的。状态转移方程优化为：mi,j=maxmi+1,j, mi,j-1+ti,j ij规划的边界条件是： mi,i=0算法的时间复杂度 O(n2)。Back
