算法合集之动态规划算法时间效率的优化.pptx

算法合集之动态规划算法时间效率的优化;动态规划算法的时间复杂度=;一、减少状态总数;例一、 Raucous Rockers 演唱组（USACO`96）;设n首歌曲按照创作顺序排序后的长度为long[1..n]，则动态规划的状态表示描述为：;改进的状态表示描述为： g[i,j]=(a, b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲首录制所需的最少唱片为：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)};例三、石子合并问题(NOI`95) [问题描述];ij 规划的边界条件为：m[i,i]=0 令s[i,j]=k，表示合并的最优断开位置。算法的时间复杂度为O(n3)。;合并第i堆到第j堆石子的最优断开位置s[i,j]要么等于i，要么等于j-1，也就是说最优合并方案只可能是：;状态转移方程优化为：;例三、LOSTCITY (NOI`2000);我们分别用v,u,a表示动词，名词和辅词，给出的文章用L[1..M]表示，则状态表示描述为：;