动态规划算法初步(修改)指南.ppt

优化：贪心+二分 因为如果处理到i位置，而且i位置之前有多个合法序列的长度为x，那么最后一个数越小，这个序列必定就越优。 我们可以用用g[k]表示当前长度为k的合法序列中最后一位的最小值，那么显然g是单调上升的。 之后我们就可以利用g快速地求出f[i]，具体方法是：用二分找到最大的k，并且要满足g[k]a[i]，那么f[i]=k+1，并一直用a[i]更新g[k+1]，使数列g始终最优。 时间复杂度就降为O(n log n) 优化一： 在刚刚的算法中，我们需要一个包含10^4*10^4个int64的数组f，显然要超内存，所以不可行 我们发现求解f[i]只需要知道f[i-1]就够了，而剩下的f[0]~f[i-2]是没有用的，所以我们可以用滚动数组对它进行压缩，动态转移方程为f[i and 1,j]=max{f[i and 1 xor 1,j], f[i and 1 xor 1,j-w[i]]+v[i]} 这样，空间复杂度就降为O(2m) 优化二： 在插入i-1个物品后，我们得到一维数组f[j]表示前i-1个物品占用j的空间，可以获得的最大价值。 插入第i个物品时f[j]=max{f[j],f[j-w[i]]-v[i]} 但是看似简洁的式子是会有问题的，可能首先更新了f[j]，又用新的f[j]更新f[j+w[i]]，也就是说物品i被使用了多次。 逆序可以解决上述问题。 空间复杂度为O(m) 5堆石子： * (1,5)=min{ (1,1)+(2,5); (1,2)+(3,5)； (1,3)+(4,5); (1,4)+(5,5)}+sum[1,5] n 堆石子：n-1次合并 * a1,a2,a3,…,an-1,an Min{(1..k)+(k+1..n)} +sum[1,n] 枚举：k=1..n-1 重叠子问题和最优子结构性质 (1,n)=min{ (1,1)+(2,n); (1,2)+(3,n)； … (1,n-1)+(n,n)}+sum[1,n] 动态规划算法： * 定义f[i,j]表示从第i到第j堆间合并为一堆的最小代价。 a[i],……,a[j] 共有j-i+1堆石子 sum[i,j]=a[i]+a[i+1]+…+a[j] 状态转移方程：f[i,j]:={f[i,k]+f[k+1,j]}+sum[i,j] 枚举位置k：i=k=j-1 初始：f[i,i]=0; ans=f[1,n] 实现方法1：记忆化有哪些信誉好的足球投注网站 * a[i]:记录第i堆石子数量。 s[i]=a[1]+a[2]+…+a[i]。//前缀和 sum[i,j]=s[j]-s[i-1]. readln(n); s[0]:=0; for i:=1 to n do begin read(a[i]); s[i]:=s[i-1]+a[i]; end; 有哪些信誉好的足球投注网站过程： * function dfs(i,j:longint):longint;//合并i..j var k:longint; begin if i=j then exit(0);// 初始f[i,j]:=0; if f[i,j]0 then exit(f[i,j]);//已经求过 f[i,j]:=maxlongint;//为求最小值准备 for k:=i to j-1 do f[i,j]:=min(f[i,j], dfs(i,k)+dfs(k+1,j)+s[j]-s[i-1]); exit(f[i,j]); // dfs=f[i,j] 返回函数值 end; * 0 7 20 36 47 61 0 10 25 34 48 0 11 20 34 0 7 17 0 6 0 3 4 6 5 2 4 1 2 3 4 5 6 1 2 3 4 5 6 f[i,j]:第i到第j堆间合并为一堆的最小代价。 f[i,j]:={f[i,k]+f[k+1,j]}+sum[i,j] * f[2,5]=min(f[2,2]+f[3,5];f[2,3]+f[4,5];f[2,4]+f[5,5])+sum[2,5]=min(20,10+7,25)+17=34 递推法：合并第 i堆 到第 j堆 * for i:=1 to n do f[i,i]:=0;{初始化} for p:=1 to n-1 do //合并的堆数p: 阶段 for i:=1 to n-p do //枚举状态： begin j:=i+p; f[i,j]:=maxlongint; for k:=i to