文档介绍：动态规划详解第一章
首先让我们看一个例子：
例1:如下图有一个数字三角阵，请编一个程序计算从顶点至底的某处的一条路径，使该路
径所经过的数字的和最大。每一步可沿左斜线向下或右斜线向下走。 嘲郛闰属钞瘗睐杨***赖雷蝴!。
7
5 3
通过状态转移方程得来，
与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。 坛搏乡it忏篓锲铃
演跻耿金勺。
<<<<<<<<<<<<<<<<<<<end>>>>>>>>>>>>>>>>>>
经典题目推荐：
.最长不下降子序列 O(NA2)版本
.最长公共子序列
.最小字母代价树
.石子合并
.最优二叉树
.工作安排
.背包问题
.加分二叉树
.钱币问题
动态规划详解第二章
通过上一章的学****相信大家对动态规划已经有了一个初步的了解， 如果您将上一章的推荐<br****题全部掌握，那么您可以开始这一章的学****内容了。
这一章，我们将讲解一些动态规划的设计技巧。
相信大家在做动态规划一类题目的时候， 往往不容易看出来这道题目是动态规划。 其实这并
不是，^的IQ低，几乎所有的初学者都会存在这样的问题，我同样也不例外，不过凭借我超 人的天赋，终于总结出来如何看出来某道题是不是动态规划的终极方法：
做题做题在做题！在一年半的学****中，我深刻的体会到了：动态规划是做出来的！ 这个硬道
理，没有题目数量的保证，学好动态规划是很困难的。
但是动态规划也并非是无章可循，下面就为大家介绍几种常见的类型：
.极值问题
这类问题的显著特征就是让您求出最 X值，并且往往具有最后子结构的性质，因为其模型
变化丰富，并且和实际联系紧密，所以在动态规划类问题中占有很大的重量
.总数问题
. 一类博弈问题
.某些杂题
一般情况下，动态规划类的问题往往就这几种类型，因此当大家看到以上几种类型的时候， 不妨向动态规划的方向作些思考。
学****动态规划的另一个难点就是状态的设计， 可以说，只要有了状态，那么决策和阶段也就
迎刃而解了。
一个好的状态，首先要把问题描述清楚，其次转移的时候应当尽量 简单”，这里的简单，主
要指状态之间的 距离”，譬如A[I]=MAX（A[J]） J<=I 就没有A[I]=A[I-1]好。
下面让我们看一道题目：
例：排队买票
问题描述：一场演唱会即将举行。现有 N （O〈N〈=200〉个歌迷排队买票，一个人买一张，
而售票处规定，一个人每次最多只能买两张票。 假设第I位歌迷买一张票需要时间 Ti（1 <=I
<=n>,队伍中相邻的两位歌迷（第 j个人和第j+1个人）可以由前一个人买两张票，也可 由后一位买两张票，则另一位就可以不用排队了，则这两位歌迷买两张票的时间变为 Rj,
现给出N, Tj和Rj,求使每个人都买到票的最短时间和方法。
因为可以从前一个人买票，又可以从后一个人买票，似乎不符合无后效性的原则， 没有办法
用动态规划求解。
所以我们不妨采用加一维的策略：
设F （I, **）为到第i个人为止所需的最短时间.
设Ti为第I个人单独买票的时间。
设Ri为第I个人买2张票的时间。
则：状态转移方程分 5种情况：
F （I,仅买1张）=MIN{F （I-1，仅买1张），F （I-1 ,买2张代前一位），F （ I-1 ,不买