文档介绍：动态规划算法时间效率的优化福州第三中学毛子青动态规划算法的时间复杂度= 状态总数*每个状态转移的状态数*每次状态转移的时间一、减少状态总数二、减少每个状态转移的状态数三、减少状态转移的时间 1、改进状态表示; (例一) 1、减少决策时间(例三) 方法:采用恰当的数据结构; 2、减少计算递推式的时间方法:进行预处理,利用计算结果等; 2、其他方法:选取恰当的规划方向等; 1、根据最优解的性质减少决策量; (例二) 2、其他方法:利用四边形不等式证明决策的单调性等; 例一、 Raucous Rockers 演唱组( USACO`96 ) [问题描述] 现有 n 首由 Raucous Rockers 演唱组录制的歌曲,计划从中选择一些歌曲来发行 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(n 2)。 Back 例三、石子合并问题( NOI`95) [问题描述] 在一个操场上摆放着一圈 n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 2 堆石子合并成新的一堆, 并将新的一堆的石子数记为该次合并的得分。试编程求出将 n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。本例只考虑最大得分。??? jikkdjit][],[ ]},[],1[],[{],[ max 1jitjkmkim jim jki??????? i<j 规划的边界条件为: m[i,i]=0 令 s[i,j]=k ,表示合并的最优断开位置。算法的时间复杂度为 O(n 3)。设各堆的石子数依次为 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) (j) } 证明:设合并第 i堆到第 j堆石子的最优断开位置 s[i,j]=p ,且 i<p<j-1 。情况 1、 t[i, p] ≤ t[p+1,j] 由于 i<p ,所以可以设 q=s[i,p] 。于是最优合并方案为: { [ ( i… q) (q+1...p) ] (p+1 … j) } 它的得分 F 1 =m[i, q]+m[q+1,p]+m[p+1,j]+t[i, j]+ t[i, p] t[i, p] 我们可以构造如下的合并方案: { ( i… q) [ (q+1...p) (p+1 … j) ] } 它的得分 F 2 =m[i, q]+m[q+1,p]+m[p+1,j]