动态规划的理论基础是什么

动态规划的理论基础是什么

动态规划法是系统分析中一种常用的方法。在水资源规划中往往涉及到地表水库调度、水资源量的合理分配、优化调度等问题而这些问题又可概化为多阶段决策过程问题。动态规划法是解决此类问题的有效方法。动态规划法是20世纪50年代由贝尔曼等人提出，用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程就是把研究问题分成若干个相互联系的阶段，由每个阶段都作出决策，从而使整个过程达到最优化。许多实际问题利用动态规划法处理，常比线性规划法更为有效，特别是对于那些离散型问题

200分求动态规划详解！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

嗯···我学动归不是很久，同样是迷惘过，估计两个月前刚刚开窍……
你看他写的什么无后效性什么最优子结构的就头大，我也头大%…………
动态规划一般解决两类问题，一类是最优化问题,就是问你最大价值最小数什么的，另一类是方案总数问题。
细分的话类型很多，
我见得多的（我是高二学生，目前在筹备NOIP）
（你那题多我就只说名字了）
背包，楼上连9讲都放上来了我就不多说了……
最长不上升不下降子序列问题（比如说潘帕斯雄鹰生日模拟赛的飞翔，就是很经典的不下降的变形）
资源分配问题（比如说橱窗布置，马棚问题，机器分配问题）
区间动归（乘积最大，能量项链等等）
最长公共子序列问题（有个遗传编码好像）；
解决方案树的比如说爬楼梯问题……………………
动态规划的类型很多很多，因为他很灵活的，我们老师曾经给我们找了100个DP方程，但是那都没有用，强记根本记不住，关键是理解。
深入一点的就有DP的优化，时间空间的降维（就是用别的方法去做，或者比如说背包本来是二维的空间优化过该成一维的了），树形DP（这个我也不会）。
（优化里面有个很经典的题《过河》）
我对DP是属于那种突然就开了窍的……别看说“动态规划”什么的唬人，其实就是一个比较一个计算，知道他干什么了题上来就有头绪，方程啊思想啊就有了……
主要也是多看题吧，从简单的开始，理解他的思想……自己写动归的时候注意下面几个问题：
1、大前提是确定你做的是动归题……看得多了也就知道自己面对的是什么类型的题了
2、次前提是想法要对（我做题的时候先想这道题时间空间的维度，然后根据这个去想方程），方程正确，
实在想不起来可以先看题解，去理解人家的思想之后，不要看标程把程序做出来……
3、注意数组不要开的过小，一般都是左右都开大一点，比如他的数据范围是1~100 ，数组就开0~101.这个是防越界的，因为很多DP赋初值的时候会用到F[0],F[0,0]
4、初始值要正确，因为很多DP其他地方都是正确的因为初始值赋错了而全部过不了的情况是很常见的……（比如说USACO里面的货币系统）
5、DP循环的范围要正确，一般根据题来判断范围写多少的（比如说橱窗问题，今天下午写这个题因为循环写错了一直AC不了）
USACO里也有很多DP题，可以做……
以上全部手打，希望能对你有所帮助。
我也是正在学习的人，上面的东西不一定全部正确，但是对我而言很受用，也算是我的经验了。希望日后能一起学习交流外加进步喽
QQ：340131980
1.资源问题1
-----机器分配问题
F[I,j]:=max(f[i-1,k]+w[i,j-k])
2.资源问题2
------01背包问题
F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]);
3.线性动态规划1
-----朴素最长非降子序列
F:=max{f[j]+1}
4.剖分问题1
-----石子合并
F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
5.剖分问题2
-----多边形剖分
F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a);
6.剖分问题3
------乘积最大
f[i,j]:=max(f[k,j-1]*mult[k,i]);
7.资源问题3
-----系统可靠性(完全背包)
F[i,j]:=max{f[i-1,j-c*k]*P[I,x]}
8.贪心的动态规划1
-----快餐问题
F[i,j,k]:=max{f[i-1,j',k']+(T-(j-j')*p1-(k-k')*p2) div p3}
9.贪心的动态规划2
-----过河 f=min{{f(i-k)} (not stone)
{f(i-k)}+1} (stone);+贪心压缩状态
10.剖分问题4
-----多边形-讨论的动态规划
F[i,j]:=max{正正 f[I,k]*f[k+1,j];
负负 g[I,k]*f[k+1,j];
正负 g[I,k]*f[k+1,j];
负正 f[I,k]*g[k+1,j];}g为min
11.树型动态规划1
-----加分二叉树 (从两侧到根结点模型)
F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}
12.树型动态规划2
-----选课 (多叉树转二叉树,自顶向下模型)
F[I,j]表示以i为根节点选j门功课得到的最大学分
f[i,j]:=max{f[t.l,k]+f[t.r,j-k-1]+c}
13.计数问题1
-----砝码称重
f[f[0]+1]=f[j]+k*w[j];
(1<=i<=n;1<=j<=f[0]; 1<=k<=a;)
14.递推天地1
------核电站问题
f[-1]:=1;f[0]:=1;
f:=2*f[i-1]-f[i-1-m]
15.递推天地2
------数的划分
f[i,j]:=f[i-j,j]+f[i-1,j-1];
16.最大子矩阵1
-----一最大01子矩阵
f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;
ans:=maxvalue(f);
17.判定性问题1
-----能否被4整除
g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false;
g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)
18.判定性问题2
-----能否被k整除
f[I,j±n mod k]:=f[i-1,j];-k<=j<=k; 1<=i<=n
20.线型动态规划2
-----方块消除游戏
f[i,i-1,0]:=0
f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),
f[i,p,k+len[j]]+f[p+1,j-1,0]}
ans:=f[1,m,0]
21.线型动态规划3
-----最长公共子串，LCS问题
f[i,j]={0(i=0)&(j=0);
f[i-1,j-1]+1(i>0,j>0,x=y[j]);
max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x<>y[j]);
22.最大子矩阵2
-----最大带权01子矩阵O(n^2*m)
枚举行的起始，压缩进数列，求最大字段和，遇0则清零
23.资源问题4
-----装箱问题(判定性01背包)
f[j]:=(f[j] or f[j-v]);
24.数字三角形1
-----朴素の数字三角形
f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);
25.数字三角形2
-----晴天小猪历险记之Hill
同一阶段上暴力动态规划
if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]
26.双向动态规划1
数字三角形3
-----小胖办证
f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])
27. 数字三角形4
-----过河卒
//边界初始化
f[i,j]:=f[i-1,j]+f[i,j-1];
28.数字三角形5
-----朴素的打砖块
f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);
29.数字三角形6
-----优化的打砖块
f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}
30.线性动态规划3
-----打鼹鼠’
f:=f[j]+1;(abs(x-x[j])+abs(y-y[j])<=t-t[j])
31.树形动态规划3
-----贪吃的九头龙
32.状态压缩动态规划1
-----炮兵阵地
Max(f[Q*(r+1)+k],g[j]+num[k])
If (map and plan[k]=0) and
((plan[P] or plan[q]) and plan[k]=0)
33.递推天地3
-----情书抄写员
f:=f[i-1]+k*f[i-2]
34.递推天地4
-----错位排列
f:=(i-1)(f[i-2]+f[i-1]);
f[n]:=n*f[n-1]+(-1)^(n-2);
35.递推天地5
-----直线分平面最大区域数
f[n]:=f[n-1]+n
:=n*(n+1) div 2 + 1;
36.递推天地6
-----折线分平面最大区域数
f[n]:=(n-1)(2*n-1)+2*n;
37.递推天地7
-----封闭曲线分平面最大区域数
f[n]:=f[n-1]+2*(n-1)
:=sqr(n)-n+2;
38递推天地8
-----凸多边形分三角形方法数
f[n]:=C(2*n-2,n-1) div n;
对于k边形
f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)
39递推天地9
-----Catalan数列一般形式
1,1,2,5,14,42,132
f[n]:=C(2k,k) div (k+1);
40递推天地10
-----彩灯布置
排列组合中的环形染色问题
f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);
41线性动态规划4
-----找数
线性扫描
sum:=f+g[j];
(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)

42线性动态规划5
-----隐形的翅膀
min:=min{abs(w/w[j]-gold)};
if w/w[j]<gold then inc(i) else inc(j);
43剖分问题5
-----最大奖励
f:=max(f,f[j]+(sum[j]-sum)*i-t
44最短路1
-----Floyd
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];
45剖分问题6
-----小H的小屋
F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);
46计数问题2
-----陨石的秘密（排列组合中的计数问题）
Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];
F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);
47线性动态规划
------合唱队形
两次F:=max{f[j]+1}＋枚举中央结点
48资源问题
------明明的预算方案：加花的动态规划
f[i,j]:=max(f[i,j],f[l,j-v-v[fb]-v[fa]]+v*p+v[fb]*p[fb]+v[fa]*p[fa]);
49资源问题
-----化工场装箱员
50树形动态规划
-----聚会的快乐
f[i,2]:=max(f[i,0],f[i,1]);
f[i,1]:=sigma(f[t^.son,0]);
f[i,0]:=sigma(f[t^.son,3]);
51树形动态规划
-----皇宫看守
f[i,2]:=max(f[i,0],f[i,1]);
f[i,1]:=sigma(f[t^.son,0]);
f[i,0]:=sigma(f[t^.son,3]);
52递推天地
-----盒子与球
f[i,1]:=1;
f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);
53双重动态规划
-----有限的基因序列
f:=min{f[j]+1}
g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j])
54最大子矩阵问题
-----居住空间
f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),
min(f[i,j,k-1],f[i-1,j-1,k])),
min(min(f[i-1,j,k-1],f[i,j-1,k-1]),
f[i-1,j-1,k-1]))+1;
55线性动态规划
------日程安排
f:=max{f[j]}+P[I]; (e[j]<s)
56递推天地
------组合数
C[I,j]:=C[i-1,j]+C[I-1,j-1]
C[I,0]:=1
57树形动态规划
-----有向树k中值问题
F[I,r,k]:=max{max{f[l,I,j]+f[r,I,k-j-1]},f[f[l,r,j]+f[r,r,k-j]+w[I,r]]}
58树形动态规划
-----CTSC 2001选课
F[I,j]:=w(if i∈P)+f[l,k]+f[r,m-k](0≤k≤m)(if l<>0)
59线性动态规划
-----多重历史
f[i,j]:=sigma{f[i-k,j-1]}(if checked)
60背包问题(+-1背包问题+回溯)
-----CEOI1998 Substract
f[i,j]:=f[i-1,j-a] or f[i-1,j+a]
61线性动态规划(字符串)
-----NOI 2000 古城之谜
f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1}f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+words[s]}
62线性动态规划
-----最少单词个数
f[i,j]:=max{f[I,j],f[u-1,j-1]+l}
63线型动态规划
-----APIO2007 数据备份
状态压缩＋剪掉每个阶段j前j*2个状态和j*2+200后的状态贪心动态规划
f:=min(g[i-2]+s,f[i-1]);
64树形动态规划
-----APIO2007 风铃
f:=f[l]+f[r]+{1 (if c[l]<c[r])}
g:=1(d[l]<>d[r]) 0(d[l]=d[r])
g[l]=g[r]=1 then Halt;
65地图动态规划
-----NOI 2005 adv19910
F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];
66地图动态规划
-----优化的NOI 2005 adv19910
F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;
67目标动态规划
-----CEOI98 subtra
F[I,j]:=f[I-1,j+a] or f[i-1,j-a]
68目标动态规划
----- Vijos 1037搭建双塔问题
F[value,delta]:=g[value+a,delta+a] or g[value,delta-a]
69树形动态规划
-----有线电视网
f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j])
leaves>=p>=l, 1<=q<=p;
70地图动态规划
-----vijos某题
F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]);
71最大子矩阵问题
-----最大字段和问题
f:=max(f[i-1]+b,b); f[1]:=b[1]
72最大子矩阵问题
-----最大子立方体问题
枚举一组边i的起始，压缩进矩阵 B[I,j]+=a[x,I,j]
枚举另外一组边的其实，做最大子矩阵
73括号序列
-----线型动态规划
f[I,j]:=min(f[I,j],f[i+1,j-1](ss[j]=”()”or(”[]”)),
f[I+1,j+1]+1 (s[j]=”(”or”[” ] , f[I,j-1]+1(s[j]=”)”or”]” )
74棋盘切割
-----线型动态规划
f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],
f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]
min{}}
75概率动态规划
-----聪聪和可可(NOI2005)
x:=p[p[i,j],j]
f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1
f[I,i]=0
f[x,j]=1
76概率动态规划
-----血缘关系
F[A, B]=(f[A0, B]+P[A1, B])/2
f[I,i]=1
f[I,j]=0(I,j无相同基因)
77线性动态规划
-----决斗
F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j
78线性动态规划
-----舞蹈家
F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]])
79线性动态规划
-----积木游戏
F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k’],f[I,a+1,a+1,k’])
80树形动态规划（双次记录）
-----NOI2003 逃学的小孩
朴素的话枚举节点i和离其最远的两个节点 j,k O(n^2)
每个节点记录最大的两个值，并记录这最大值分别是从哪个相邻节点传过来的。当遍历到某个孩子节点的时候，只需检查最大值是否是从该孩子节点传递来的。如果是，就取次大，否则取最大值
81树形动态规划(完全二叉树)
-----NOI2006 网络收费
F[I,j,k]表示在点i所管辖的所有用户中，有j个用户为A，在I的每个祖先u上，如果N[a]>N则标0否则标1，用二进制状态压缩进k中，在这种情况下的最小花费
F[I,j,k]:=min{f[l,u,k and (s<<(i-1))]+w1,f[r,j-u,k and(s<<(i-1))]}
82树形动态规划
-----IOI2005 河流
F:=max
83记忆化搜索
-----Vijos某题,忘了
F[pre,h,m]:=sigma{SDP(I,h+1,M+i)}(pre<=i<=M＋1)
84状态压缩动态规划
-----APIO 2007 动物园
f[I,k]:=f[i-1,k and not (1<<4)] + NewAddVal
85树形动态规划
-----访问术馆
f[i,j-c×2]:= max ( f[l,k], f[r,j-c×2-k] )
86字符串动态规划
-----Ural 1002 Phone
if exist(copy(s,j,i-j)) then f:=min(f,f[j]+1);
87多进程动态规划
-----CEOI 2005 service
Min( f[i,j,k], f[i-1,j,k] + c[t[i-1],t] )
Min( f[i,t[i-1],k], f[i-1,j,k] + c[j,t] )
Min( f[i,j,t[i-1]], f[i-1,j,k] + c[k,t] )
88多进程动态规划
-----Vijos1143 三取方格数
max(f[i,j,k,l],f[i-1,j-R[m,1],k-R[m,2],l-R[m,3]]);
if (j=k) and (k=l) then inc(f[i,j,k,l],a[j,i-j]) else
if (j=k) then inc(f[i,j,k,l],a[j,i-j]+a[l,i-l]) else
if (k=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else
if (j=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else
inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]+a[l,i-l]);
89线型动态规划
-----IOI 2000 邮局问题
f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]);
90线型动态规划
-----Vijos 1198 最佳课题选择
if j-k>=0 then Min(f[i,j],f[i-1,j-k]+time(i,k));
91背包问题
----- USACO Raucous Rockers
多个背包，不可以重复放物品，但放物品的顺序有限制。
F[I,j,k]表示决策到第i个物品、第j个背包，此背包花费了k的空间。
f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t])
92多进程动态规划
-----巡游加拿大（IOI95、USACO）
d[i,j]=max{d[k,j]+1(a[k,i] & j<k<i),d[j,k]+1(a[I,j] & (k<j))}。
f[i,j]表示从起点出发，一个人到达i，另一个人到达j时经过的城市数。d[i,j]=d[j,i]，所以我们限制i>j
分析状态(i,j)，它可能是(k,j)(j<k<i)中k到达i得到（方式1），也可能是(j,k)(k<j)中k超过j到达i得到（方式2）。但它不能是(i,k)(k<j)中k到达j得到，因为这样可能会出现重复路径。即使不会出现重复路径，那么它由(j,k)通过方式2同样可以得到，所以不会遗漏解 时间复杂度O(n3)
93动态规划
-----ZOJ cheese
f[i,j]:=f[i-kk*zl[u,1],j-kk*zl[u,2]]+a[i-kk*zl[u,1],j-kk*zl[u,2]]
94动态规划
-----NOI 2004 berry 线性
F[I,1]:=s
F[I,j]:=max{min{s-s[l-1]},f[l-1,j-1]} (2≤j≤k, j≤l≤i)
95动态规划
-----NOI 2004 berry 完全无向图
F[I,j]:=f[i-1,j] or (j≥w) and (f[i-1,j-w])
96动态规划
-----石子合并 四边形不等式优化
m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j]
97动态规划
-----CEOI 2005 service
（k≥long，i≥1）g[i, j, k]=max{g[i-1,j,k-long]+1，g[i-1,j,k]}
（k<long，i≥1） g[i, j, k]=max{g[i-1,j-1,t-long]+1，g[i-1,j,k]}
(0≤j≤m， 0≤k<t) g[0,j,k]=0;
ans:=g[n,m,0]。
状态优化：g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long}
其中(a, b)+long=(a’, b’)的计算方法为：
当b+long ≤t时： a’=a; b’=b+long;
当b+long ＞t时： a’=a+1; b’=long;
规划的边界条件：
当0≤i≤n时，g[i,0]=(0,0)
98动态规划
-----AHOI 2006宝库通道
f[k]:=max{f[k-1]+x[k,j]-x[k,i-1], x[k,j]-x[k,i-1]}
99动态规划
-----Travel
A) 费用最少的旅行计划。
设f表示从起点到第i个旅店住宿一天的最小费用；g表示从起点到第i个旅店住宿一天，在满足最小费用的前提下所需要的最少天数。那么：
f=f[x]+v,g=g[x]+1
x满足：
1、x<i，且d – d[x] <= 800（一天的最大行程）。
2、对于所有的t < i, d – d[t] <= 800，都必须满足：
A. g[x] < g[t](f[x] = f[t]时) B. f[x] < f[t](其他情况)
f[0] = 0，g[0] = 0。 Ans:=f[n + 1]，g[n+1]。
B). 天数最少的旅行计划。
方法其实和第一问十分类似。
设g’表示从起点到第i个旅店住宿一天的最少天数；f’表示从起点到第i个旅店住宿一天，在满足最小天数前提下所需要的最少费用。那么：
g’ = g’[x] + 1,f’ = f’[x] + v
x满足：
1、x<i，且d – d[x] <= 800（一天的最大行程）。
2、对于所有的t < i, d – d[t] <= 800，都必须满足：
f’[x] < f’[t] g’[x] = g’[t]时
g’[x] < g’[t]其他情况
f’[0] = 0，g’[0] = 0。 Ans:=f’[n + 1]，g’[n+1]。
100动态规划
-----NOI 2007 cash
y:=f[j]/(a[j]*c[j]+b[j]);
g:=c[j]*y*a+y*b;
f:=max(f,g)

动态规划的推法 谢谢

DP是把一个很大的有阶段性有最佳答案问题分割成许多子问题，每个子问题有自己的最优情况（最优子结构），也就是说，每个动态规划的问题都是有许多最有子结构接和起来的，而推法就是要分割出最有子结构
然后对这个小问题得出最优的答案，并由此推出全局的最优解
1.最优子结构性质；
设Q[i,j]表示第i颗珠子到第j颗珠子合并所产生的能量。显然Q[1,n]表示的是合并产生的总的能量。给定一种标号方法，maxQ[1,n]就是所要求的。设最后一次合并在k处进行，则有Q[1,n]＝Q[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]。要Q[1,n]最大，必然要Q[1,k]，Q[k+1,n]最大。
证明：假设Q[1,k]不是最大，则必然存在一Q'[1,k]>Q[1,k]。那么就有Q'[1,n]＝Q'[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]>Q[1,k]。这与Q[1,n]的最优性矛盾
能量项链其实就是石子合并
算法分析
竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并：从最上面
的一堆开始，沿顺时针方向排成一个序列。 第一次选得分最小（最大）的相邻两堆合并，
形成新的一堆；接下来，在N－1堆中选得分最小（最大）的相邻两堆合并……，依次类推，
直至所有石子经N－1次合并后形成一堆。
例如有6堆石子，每堆石子数（从最上面一堆数起，顺时针数）依次为3 46 5
4 2
（图6.2-5）
要求选择一种合并石子的方案，使得做5次合并，得分的总和最小。
按照贪心法，合并的过程如下：
每次合并得分
第一次合并 3 4 6 5 4 2 5
第二次合并 5 4 6 5 4 9
第三次合并 9 6 5 4 9
第四次合并 9 6 9 15
第五次合并 15 9 24
24
总得分＝5＋9＋9＋15＋24＝62
但是当我们仔细琢磨后，可得出另一个合并石子的方案：
每次合并得分
第一次合并 3 4 6 5 4 2 7
第二次合并 7 6 5 4 2 13
第三次合并 13 5 4 2 6
第四次合并 13 5 6 11
第五次合并 13 11 24
24
总得分＝7＋6＋11＋13＋24＝61
显然，后者比贪心法得出的合并方案更优。 题目中的示例故意造成一个贪心法解题的
假像，诱使读者进入“陷阱”。为了帮助读者从这个“陷阱”里走出来， 我们先来明确一
个问题：
1．最佳合并过程符合最佳原理
使用贪心法至所以可能出错， 是因为每一次选择得分最小（最大）的相邻两堆合并，
不一定保证余下的合并过程能导致最优解。聪明的读者马上会想到一种理想的假设：如果N
－1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N－1次合并后
的得分总和必然是最优的。
例如上例中第五次合并石子数分别为13和11的相邻两堆。 这两堆石头分别由最初
的第1，2，3堆（石头数分别为3，4，6）和第4，5，6堆（石头数分别为5，4，
2）经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N－2 次合并的得分
总和最优。为了实现这一目标，我们将第1个序列又一分为二：第1、2堆构成子序列1，
第3堆为子序列2。第一次合并子序列1中的两堆，得分7； 第二次再将之与子序列2的
一堆合并，得分13。显然对于第1个子序列来说，这样的合并方案是最优的。同样，我
们将第2个子序列也一分为二；第4堆为子序列1，第5，6堆构成子序列2。第三次合
并子序列2中的2堆，得分6；第四次再将之与子序列1中的一堆合并，得分13。显然
对于第二个子序列来说，这样的合并方案也是最优的。 由此得出一个结论——6堆石子经
过这样的5次合并后，得分的总和最小。
我们把每一次合并划分为阶段，当前阶段中计算出的得分和作为状态， 如何在前一次
合并的基础上定义一个能使目前得分总和最大的合并方案作为一次决策。很显然，某阶段
的状态给定后，则以后各阶段的决策不受这阶段以前各段状态的影响。 这种无后效性的性
质符最佳原理，因此可以用动态规划的算法求解。
2．动态规划的方向和初值的设定
采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。 这些石子堆子序
列包括：
｛第1堆、第2堆｝、｛第2堆、第3堆｝、……、｛第N堆、第1堆｝；
｛第1堆、第2堆、第3堆｝、｛第2堆、第3堆、第4堆｝、……、｛第N堆、第1
堆、第2堆｝；
……
｛第1堆、……、第N堆｝｛第1堆、……、第N堆、第1堆｝……｛第N堆、第1堆、
……、第N－1堆｝
为了便于运算，我们用〔i，j〕表示一个从第i堆数起，顺时针数j堆时的子序列
｛第i堆、第i＋1堆、……、第（i＋j－1）mod n堆｝
它的最佳合并方案包括两个信息：
①在该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和；
②形成最佳得分和的子序列1和子序列2。由于两个子序列是相邻的， 因此只需记住
子序列1的堆数；
设
f〔i，j〕——将子序列〔i，j〕中的j堆石子合并成一堆的最佳得分和；
c〔i，j〕——将〔i，j〕一分为二，其中子序列1的堆数；
（1≤i≤N，1≤j≤N）
显然，对每一堆石子来说，它的
f〔i，1〕＝0 c〔i，1〕＝0 （1≤i≤N）
对于子序列〔i，j〕来说，若求最小得分总和，f〔i，j〕的初始值为∞； 若求最大得
分总和，f〔i，j〕的初始值为0。（1≤i≤N，2≤j≤N）。
规划的方向是顺推。先考虑含二堆石子的N个子序列（各子序列分别从第1堆、第2堆、
……、第N堆数起，顺时针数2堆）的合并方案
f〔1，2〕，f〔2，2〕，……，f〔N，2〕
c〔1，2〕，c〔2，2〕，……，c〔N，2〕
然后考虑含三堆石子的N个子序列（各子序列分别从第1堆、第2堆、……、第N堆
数起，顺时针数3堆）的合并方案
f〔1，3〕，f〔2，3〕，……，f〔N，3〕
c〔1，3〕，c〔2，3〕，……，c〔N，3〕
……
依次类推，直至考虑了含N堆石子的N个子序列（各子序列分别从第1堆、第2堆、 …
…、第N堆数起，顺时针数N堆）的合并方案
f〔1，N〕，f〔2，N〕，……，f〔N，N〕
c〔1，N〕，c〔2，N〕，……，c〔N，N〕
最后，在子序列〔1，N〕，〔2，N〕，……，〔N，N〕中，选择得分总和（f值）最
小（或最大）的一个子序列〔i，N〕（1≤i≤N），由此出发倒推合并过程。
3．动态规划方程和倒推合并过程
对子序列〔i，j〕最后一次合并，其得分为第i堆数起，顺时针数j堆的石子总数t。被
合并的两堆石子是由子序列〔i，k〕和〔（i＋k－1）modn＋1，j－k〕（1≤k≤j－1）
经有限次合并形成的。为了求出最佳合并方案中的k值，我们定义一个动态规划方程：
当求最大得分总和时
f〔i，j〕＝max｛f〔i，k〕＋f〔x，j-k〕＋t｝
1≤k≤j－1
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（2≤j≤n，1≤i≤n）
当求最小得分总和时
f〔i，j〕＝min｛f〔i，k〕＋f〔x，j－k〕＋t｝
1≤k≤j－1
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（2≤j≤n，1≤i≤n）
其中x＝（i＋k－1）modn＋1，即第i堆数起，顺时针数k＋1堆的堆序号。
例如对（图6．2－4）中的6堆石子，按动态规划方程顺推最小得分和。 依次得出含
二堆石子的6个子序列的合并方案
f〔1，2〕＝7 f〔2，2〕＝10 f〔3 ，2〕＝11
c〔1，2〕＝1 c〔2，2〕＝1 c〔3，2〕＝1
f〔4，2〕＝9 f〔5，2〕＝6 f〔6，2〕＝5
c〔4，2〕＝1 c〔5， 2〕＝1 c〔6，2〕＝1
含三堆石子的6个子序列的合并方案
f〔1，3〕＝20 f〔2，3〕＝25 f〔3，3〕＝24
c〔1，3〕＝2 c〔2，3〕＝2 c〔3，3〕＝1
f〔4，3〕＝17 f〔5，3〕＝14 f〔6，3〕＝14
c〔4，3〕＝1 c〔5，3〕＝1 c〔6，3〕＝2
含四堆石子的6个子序列的合并方案
f〔1，4〕＝36 f〔2，4〕＝38 f〔3，4〕＝34
c〔1，4〕＝2 c〔2，4〕＝2 c〔3，4〕＝1
f〔4，4〕＝28 f〔5，4〕＝26 f〔6，4〕＝29
c〔4，4〕＝1 c〔5，4〕＝2 c〔6，4〕＝3
含五堆石子的6个子序列的合并方案
f〔1，5〕＝51 f〔2，5〕＝48 f〔3，5〕＝45
c〔1，5〕＝3 c〔2，5〕＝2 c〔3，5〕＝2
f〔4，5〕＝41 f〔5，5〕＝43 f〔6，5〕＝45
c〔4，5〕＝2 c〔5，5〕＝3 c〔6，5〕＝3
含六堆石子的6个子序列的合并方案
f〔1，6〕＝61 f〔2，6〕＝62 f〔3，6〕＝61
c〔1，6〕＝3 c〔2，6〕＝2 c〔3，6〕＝2
f〔4，6〕＝61 f〔5，6〕＝61 f〔6，6〕＝62
c〔4，6〕＝3 c〔5，6〕＝4 c〔6，6〕＝3
f〔1，6〕是f〔1，6〕，f〔2，6〕，……f〔6，6〕中的最小值，表明最小
得分和是由序列〔1，6〕经5次合并得出的。我们从这个序列出发， 按下述方法倒推合
并过程：
由c〔1，6〕＝3可知，第5次合并的两堆石子分别由子序列〔1，3〕和子序列〔
4，3〕经4次合并后得出。其中
c〔1，3〕＝2可知由子序列〔1，3〕合并成的一堆石子是由子序列〔1，2〕和
第三堆合并而来的。而c〔1，2〕＝1，以表明了子序列〔1，2〕的合并方案是第1堆
合并第2堆。
由此倒推回去，得出第1，第2次合并的方案
每次合并得分
第一次合并 3 4 6…… 7
第二次合并 7 6…… 13
13……
子序列〔1，3〕经2次合并后合并成1堆， 2次合并的得分和＝7＋13＝20。
c〔4，3〕＝1，可知由子序列〔4，3〕合并成的一堆石子是由第4堆和子序列〔5，
2〕合并而来的。而c〔5，2〕＝1，又表明了子序列〔5，2〕的合并方案是第5堆合
并第6堆。由此倒推回去，得出第3、第4次合并的方案
每次合并得分
第三次合并 ……54 2 6
第四次合并 ……5 6 11
……11
子序列〔4，3〕经2次合并后合并成1堆，2次合并的得分和＝6＋11＝17。
第五次合并是将最后两堆合并成1堆，该次合并的得分为24。
显然，上述5次合并的得分总和为最小
20＋17＋24＝61
上述倒推过程，可由一个print（〔子序列〕）的递归算法描述
procedure print （〔i，j〕）
begin
if j〈〉1 then ｛继续倒推合并过程
begin
print（〔i，c〔i，j〕）；｛倒推子序列1的合并过程｝
print（〔i＋c〔i，j〕－1）mod n＋1，j－c〔i，j〕）
｛倒推子序列2的合并过程｝
for K：＝1 to N do｛输出当前被合并的两堆石子｝
if （第K堆石子未从圈内去除）
then begin
if（K＝i）or（K＝X）then置第K堆石子待合并标志
else第K堆石子未被合并；
end；｛then｝
第i堆石子数←第i堆石子数＋第X堆石子数；
将第X堆石子从圈内去除；
end；｛then｝
end；｛print｝
例如，调用print（〔1，6〕）后的结果如下：
print（〔1，6〕）⑤
│
┌——————┴——————┐
│ │
print（〔1，3〕）② print（〔4，3〕）④
│ │
print（〔1，2〕）① ┌—————┴—————┐
│ │ │
│
┌—————┴—————┐ print（〔4，1〕） print（〔5，2〕）③
│ │ │
print（〔1，1〕） print（〔2，1〕） │
┌——————┴——————┐
│ │
print（〔5，1〕） print（〔6，1〕）
（图6.2-5）
其中回溯至
① 显示 3 46 5 4
② 显示 7 65 4 2
③ 显示 13 54 2
④ 显示 135 6
⑤ 显示 13 11
注:调用print过程后，应显示6堆石子的总数作为第5次合并的得分

动态规划问题

讲起来有点麻烦，我给你我的。
你看看吧！
#include<stdio.h>
#include<string.h>
struct clas{
int value,fa,next;
int son[502],number;
clas(){value=fa=number=0;memset(son,0,sizeof(son));}
};
bool choose[501][501]={false},ok[501]={false};
clas a[502];int m,n,use[502]={0},num=0,rem[502][502];
int max(int x,int y)
{
if(x>y)return x;return y;
}
int ff(int x,int k)
{
if(rem[x][k]>=0)return rem[x][k];
if(x==m+1||k==0)return 0;
int now1=ff(x+1,k-1)+a[use[x]].value;
int now2=ff(a[use[x]].next,k);
if(now1>now2){choose[x][k]=true;return rem[x][k]=now1;}
else {return rem[x][k]=now2;}
}
void read(int x)
{
use[++num]=x;
for(int i=1;i<=a[x].number;i++)read(a[x].son[i]);
a[x].next=num+1;
}
void print(int x,int k)
{
if(x==m+1||k==0)return ;
if(choose[x][k]==true)
{
ok[use[x]]=true;
print(x+1,k-1);
}
else
{
print(a[use[x]].next,k);
}
}
int main()
{
freopen("course.in","r",stdin);
freopen("course.out","w",stdout);
memset(rem,-1,sizeof(rem));
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
scanf("%d%d",&a[i].fa,&a[i].value);
a[a[i].fa].son[++a[a[i].fa].number]=i;}
num=0;
for(int i=1;i<=m;i++)if(a[i].fa==0)read(i);
printf("%d ",ff(1,n));
print(1,n);
for(int i=1;i<=m;i++)if(ok[i])printf("%d ",i);
return 0;
}

声明： 我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理，本站部分文字与图片资源来自于网络，转载是出于传递更多信息之目的,若有来源标注错误或侵犯了您的合法权益，请立即通知我们(管理员邮箱：daokedao3713@qq.com)，情况属实，我们会第一时间予以删除，并同时向您表示歉意,谢谢!