文档介绍：动态规划算法时间效率的优化
动态规划算法的时间复杂度=
状态总数*每个状态转移的状态数*每次状态转移的时间
一、减少状态总数
二、减少每个状态转移的状态数
三、减少状态转移的时间
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(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) (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) }
它的得分F1=m[i, q]+m[q+1,p]+m[p+1,j]+t[i, j]+t[i, p]
我们可以构造如下的合并方案:
{ (i…q) [ (q+1...p) (p+1…j) ] }
它的得分F2=m[i, q]+m[q+1,p]+m[p+1,j]+t[i, j]+t[q+1,j]
由于q<p,所以t[i, p]≤t[p+1,j]<t[q+1,j]
所以F1<F2,这与合并第i堆到第j堆石子的最优断开位置 s[i, j]=p矛盾
情况2、t[i, p]>t[p+1,j] 与情况1是对称的。
状态转移方程优化为:
m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j] i<j
规划