文档介绍：动态规划
摘要：
动态规划是解决多阶段决策最优化问题的一种思想方法。所 谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据 每一步所选决策的不同，将随即引起状态的转移，最终在变化的 状态中产生一个决策序列。动态规划就是为了使产生的？
1） 首先，分析题意，考察此题是否满足最优化原理与无后效性两个条件。
2） 接着，确定题中的阶段，状态，及约束条件。
3） 推导出各阶段状态间的函数基本方程，进行计算。
具体求解则有多种方法。
1 前向与后向动态规划法
所谓前向与后向，指的是从起点出发，层层递推，直到终点，或从终点出发， 逆向求解。这两种方法本质上是一样的，具体解题时，可根据实际情况来选用。
[ 例 2] 排队买票
问题描述：一场演唱会即将举行。现有N （O〈N〈=200）个歌迷排队买票， 一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第I位歌迷 买一张票需要时间Ti（1〈=I〈二n）,队伍中相邻的两位歌迷（第j个人和第j+1 个人）也可以由其中一个人买两张票，而另一位就可以不用排队了，则这两位歌 迷买两张票的时间变为Rj,假如Rj〈Tj+Tj+i，则这样做就可以缩短后面歌迷等 待的时间，加快整个售票的进程。现给出N, Tj和Rj，求使每个人都买到票的最 短时间和方法。
解决问题：本题的阶段十分明显，只要按排队的先后顺序划分即可。而买票 的方式只有两种，要么一人买一张，要么一人买两张，整个过程呈线性排列。要
使前 I 个人买票时间最短，只需考虑前 I 个人的买票方式，与队列以后的人无关。 而且显而易见，在最优策略中，任意m个连续的决策也肯定是最优的。这样，问 题就符合了最优化原理及无后效性，能运用动态规划。那如何构造函数递推式 呢？可以以到每个人为止所需的最短时间为状态值，设为f (i),于是有f (i) =min{f (i-1)+Ti, f (i-2)+Ri-1}，起步时 f (0)=0，f(1)=TX。如此从 前往后，只需遍历一次即可。
上面的分析是从前往后进行的。其实倒过来逆推也一样。设f (I)表示当 票卖到第I个人时，最少还需多少时间才能卖完。则函数递推式为f (I) =min{f (I+1)+Ti，f (I+2)+Ri}，从后往前逆推，起步时 f (n)=Tn，f (n+1)=0 。
采用前向还是后向动态规划，要看实际情况而定，哪一种直观、简便，就运 用哪一种。
2 具有隐含阶段的问题(即阶段不明显)
动态规划的一个重要环节是阶段划分，可有些题目无明显阶段，但也符合最 优化原理，怎么解决呢？下面来看一道例题。
[例3] 最小费用问题
问题描述：已知从A到J的路线及费用如图3,求从A到J的最小费用路线。 图3
A
解决问题：本问题没有明显的阶段划分，，各点间没有一定的先后次序，不能 按照最少步数来决定顺序，如从A到D走捷径需4/但A-C-D只需3,更优。看 来图中出现回路，不能实施动态规划。其实不然。细想一下，从A到J的最优策 略，它每一部分也是最优的(可以用前述的反证法来证明)，换言之，本题也具 有最优化性质，只是阶段不明显而已。
对于这类问题，我们可以换个角度分析，构造算法。比较一下前面所讲的前 向与后向动态规划法，都是以某个状态为终点，寻找到达次点的路径，然后比较 优劣，确定此状态最优值。可是，本题阶段不明显，各状态之间的道路会出现嵌 套，故此法不能使用。变一下角度，每次都以某个状态为起点，遍历由它引申出 去的路径，等所有已知状态都扩展完了，再来比较所有新状态，把值最小的那个 状态确定下来，其它的不动。如图3，先从A出发，找到3个结点B，D，C，费 用为 F (B) =3，F (D) =4，F (C) =2。因为 F (B)，F (D)都大于 F (C)，那么 可以确定：不可能再有路线从B或D出发到C，比A-C更优。这样F (C)的最优 值便确定了。可是，有没有路线从C出发到B或D，比A-B或A-D更优呢？还不 清楚。继续下去，因为A扩展完了，只有从C开始，得到A-C-D=3, A-C-F=3， 于是F (D)的值被刷新了，等于3。现在，有F (B) =F (D) =F (F) =3，于是， 三点的最优值都确定下来了。然后以分别以三个点为起点，继续找。以次类推， 直到 J 点的最优值确定为止。
细心观察，其实本题的隐含阶段就是以各结点的最优值的大小来划分的，上 述过程就是按最优值从小到大前向动态规划。人们****惯上把此题归入到图论范畴
中，并将上述方法称为标号法。
动态规划的应用
上文叙述了动态规划的几种解法，下面我们通过例题来加深了解。
[例 4] 复制书稿( BOOKS)
问题描述：假设有M本书(编号为1, 2, 想将每本复制一份，M本书