文档介绍：1 5 1 3 5 10
X X
12 1 5 5 3
机器分配
准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一
总公司拥有高效生产设备M台，
定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出(f[i,j],f[k,j-1 ] +num[k+1 ,i]) num[k+l,i]表示k+1位到i位所形成的数
+1个位置上.
巴比伦塔
问题描述：
有很多的不同种类的立方体(长宽高不同)，，要求上面的一块立 方体的下底面一定要比下面的一块立方体的上底面要小，就是长和宽都要小于•问最多能建成多高的塔.
经过研究可以发现,每一种类的立方体有3种不同的摆放方式，而每种摆放方式最多用1次，所以可以分离出 3*N块“不同”的立方体，接下来,或许你仍然不知道如何动规， xi,yi,<yi或者xi>,yi, ,代价值是zi(高度).
滑雪(上海2002)
题目的大意是给出一个矩阵，如:
1
2
3
4
5
16
17
18
19
6
15
24
25
20
7
14
23
22
21
8
13
12
11
10
9
对于所给出的矩阵找出一条最长的递减链，满足链中相邻的两个元素间都是在矩阵中相邻的.
上图中所给出的矩阵中的最长链
是 1 234 25.
对于有给出的数字进行递减排序，:
F[i]:=max(F[i],F[j]+l);
满足条件是i与j在原矩阵中相邻.
试想,如果你不知道要排序，你能想到这题是用动态规划吗？
硬币问题(经典问题)
就是给出n种硬币的面值，问面值M有多少种不同的表示方法.
动态转移方程是F[i]:=F[i]+F[I-cost[j]],当前状态是i,以前状态是i-cost[j].
多米诺骨牌(某题的简化)
有N张多米诺骨牌，每张的两端有两个数字,范围在1..， 情况，.
可以这么考虑这个问题:我们把每一个骨牌的上下差值记下。接下来的任务便是将这些值分成两组，使得他 们的和的差值最小。动规过程如下：
f[O]:=true;
for i:=l to n do
for j:=sum downto a[i] do
f[j]:=fU] orfU-a[i]];
[i],j-a[i][j]表示j这个差值能否通 过组合得到。接下来的程序就不用我多说了。
商店购物(101)
.
图状动规
城堡
某国聪明美丽的公主要找一位如意郎君，她希望未来的夫君是一个聪明善良，节俭但又不吝啬的人。为了找到 理想的人选，她的爸爸一国王，给她修建了一座城堡，这个城堡有很多房间，房间之间有走廊连接，但每进入 一个房间必须要花费一定数量的钱币，公主就在某个房间中等待。开始，国王给每个候选人一样多的钱币，候 选人从同一个地点出发，直到找到美丽的公主为止，如果这时哪个人找到了公主，并且钱币刚好用完，那么他 将会赢得公主的芳心。
既然是问我们能不能到达，所以想想就应该知道,,只有出发的房间记为true.
但是,并不是以每个房间作为状态，，如果剩余的钱不一样，也 就会有不同的决策.
[i,j]来表示.
于是动态转移方程也就出来了
f[i, j]：=fri, j] or ftk, j+cti]]
K表示的是和I连接的一个房间,c[i]表示进入I号房间的花费
树状动规
没有上司的晚会
某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的上 司，要不然他们会很扫兴。现在已知每个人的活跃指数和上司关系(当然不可能存在环)，求邀请哪些人来能使 得晚会的总活跃指数最大。
按照要求构建一张关系图，可见这是一棵树。对于这类最值问题，向来是用动态规划求解的。
任何一个点的取舍可以看作一种决策，那么状态就是在某个点取的时候或者不取的时候，以他为跟的子树能有 的最大活跃总值。分