动态规划时间效率的优化

1、动态规划算法时间效率的优化福州第三中学 毛子青动态规划算法的时间复杂度二状态总数*每个状态转移的状态数*每次状态转移的时间-、减少状态总数1、改进状态表示；（例一）2、其他方法：选取恰当的规划方向等；/1、减少每个状态转移的状态数 1、根据最优解的性质减少决策量；（例二）2、其他方法：利用四边形不等式证明决策的单调性等; 、减少状态转移的时间1、减少决策时间（例三）方法：采用恰当的数据结构；2、减少计算递推式的时间方法：进行预处理，利用计算结果等；例一、 Raucous Rockers 演唱组(USACO96)问题描述现有n首由Raucous Rockers演唱组录制的歌曲，计划从中 选择一些

2、歌曲来发行m张唱片，每张唱片至多包含t分钟的音 乐，唱片中的歌曲不能重叠。按下面的标准进行选择：(1)这组唱片中的歌曲必须按照它们创作的顺序排序；(2)包含歌曲的总数尽可能多。I输入n, m, t,和n首歌曲的长度，它们按照创作顺序排序, 没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的 放在唱片中。输出所能包含的最多的歌曲数目。设n首歌曲按照创作顺序排序后的长度为longl.n,则动态 规划的状态表示描述为：gi, j, k, (0in, 0jm, 0klongi, iNl时：gi,j, k=maxgi-l,j,k-longi+l, gi-l,j,k当klongi, iNl时：gi,j,

3、 k=maxgi-l,j-l,t-longi+l, gi-l,j,k规划的边界条件为：当0jm, OSkt时：gO,j,k二0;问题的最优解为：gn,m,0 o算法的时间复杂度为：O(n*m*t)。P亍二改进的状态表示描述为：gi,j=(a, b), 0in, ji, 0am, 0bt,表示在前i首歌 曲中选取j首录制亦需的最少唱片另：a张唱片另加b分钟。 状态转移方程为：gi,j=mingi-l,j, gi-l,j-l+longi 其中(a, b)+longi=(a, b J的计算方法为: 当b+longi t时：a,=a+l; b,=longi; 规划的边界条件：当0W9时,gi90=(0

4、,0)题目所求的最大值是：answer二maxkl gn, k(m-l,t)算法的时间复杂度为：0(昭)。*Back例三、石子合并问题(NOF95)问题描述在一个操场上摆放着一圈口堆石子。现要将石子有次序地合 并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆， 并将新的一堆的石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以 及相应的合并方案。本例只考虑最大得分。设各堆的石子数依次为dl.n,则动态规划的状态表示为: li,jn,表示合并di.j所得到的最大得分： 令弟d幻,则状态转移方程为：k = i加，刀=max ，+加伙+1,刀+ /匕川ij规划的边界条件

5、为：mi,i=O令si,j=k,表示合并的最优断开位置。算法的时间复杂度为0(2)。合并第i堆到第j堆石子的最优断开位置si,j要么等于i,要么等于j-1, 也就是说最优合并方案只可能是：(i) (i+1. j) 或(i.冲 证明：设合并第i堆到第j堆石子的最优断开位置Si,j=p,且iPj-lo情况 1、ti,ptp+l,j由于ip,所以可以设q=si,po于是最优合并方案为： (i.q) (q+l.p) (p+l.j) 它的得分 Fmtil+mtq+ljpl+mtp+ljl+ttiJl+tyil我们可以构造如下的合并方案： (i .q) (q+l.p)(p+l.j) 它的得分 F2=mi,

6、q+mq+l,p+mp+lj+ti,j+tq+141由于qvp,所以ti, ptp+1 ,jtq+ l,j所以Ftp+lj与情况1是对称的。护二状态转移方程优化为：mi,j=maxmi+1 ,j, mi,j-l+ti,jij规划的边界条件是：二0算法的时间复杂度0(n2)o例三、LOSTCITY (NOF2000)问题描述现给出一张单词表、特定的语法规则和一篇文章：文章和单词表中只含26个小写英文字母a.zo单词表中的单词只有名词，动词和辅词这三种词性，且相同词 性的单词互不相同。单词的个数不超过1000,单词的长度均不 超过20。语法规则可简述为：名词短语：任意个辅词前缀接上一个名词; 动词短语：任意个辅词前缀接上一个动词；句子：以名词短语 开头，名词短语与动词短语相间连接而成。文章的长度不超过5k。且已知文章是由有限个句子组成的，句 子只包含有限个单词。编程将这篇文章划分成最少的句子，在此前提之下，要求划分 出的单词数最少。=；+十产采用不同的方法查找字符串的比较：设单词表的规模为N （N的最大值为1000）设文章的长度为M （M的最大值为5000）顺序查找二分查找哈希表检索树算法的时间 复杂度O(20*M*N)O(20*M*log2N)O(20*M