最近，我在系统的学习动态规划。其实动态规划不仅能用在信息奥赛中，它是一个非常广泛的内容且应用颇多。
本来，我还想看看数学老师究竟会怎么讲课本上的动态规划，可今年的教学大纲竟然把这么重要的一节给删掉惹。。。。
没事，大佬ycy说虽然会对我们有帮助，但是那都是很简单的内容，信息奥赛的深度比课本上的知识要多，我吐了。。。。。。
吐槽完毕
开始学习动态规划（dynamic programming）
首先，扒一些概念性的东西：
1、概念：多阶段决策过程的最优化问题
2、用途：动态规划常用于求解具有最优性质的问题
3、基本思想：将带求解问题分解成若干子问题，先求解子问题，然后从子问题的解中得到原问题的解
4、动态规划与分治法的区别：
动态规划：经分解的子问题常常不是相互独立的
分治法：就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并
区别： 分治法可以在得到子问题的答案之后逐渐累加得到原问题的解，但动态规划含有 递推的思想，若要用分治法将会重复某些子问题重复计算多次
5、多阶段决策问题
一类活动问题过程分解几个相互联系的阶段，对每一个阶段所做出的决策常常会影响下个阶段的决策。即每个决策都等同重要
6、动态规划的术语
阶段：就是将问题分解成的每个子问题，对于求解每个子问题都可以看作一个阶段
状态：表示每个阶段开始的客观条件或自然状况，就是各阶段开始时所具有“起始装备”，我们接下来要干的事情都是基于我们的“起始装备”进行的。
决策：一个阶段的状态给定之后，从该阶段到下一个阶段所进行的一个选择（行动）
策略：由每个阶段的决策所组成的序列，我们选取最优策略。也就是说我们有多种解题的思路，但我们选取最便捷最省时省空间的一种
无后效性：如果我们在给定某一阶段的状态后，则在此之后的阶段不会受到它的影响。也就是说某一阶段的所进行的的决策是决定它下一个决策的起始性质（或者说是起始状态），一旦性质（状态）决定了就不再会改
7、动态规划的基本模型
（1） 确定问题的决策对象 （明确问题想让你干什么）
（2） 对决策划分阶段 （就是说各阶段我们都是需要达到某种要求的，即以标志性条件开始和结束）
（3） 对各阶段确定状态变量 （决定以什么变量作为一个阶段，例如时间、选取物品数）
（4） 根据状态变量确定费用函数和目标函数 （我们的限制条件和目标）
（5） 建立各阶段状态变量的转移过程，确定状态转移方程 （综合上述四条得出一条全面的公式）
8、动态规划的适用条件
必须是满足最优化原理和无效性的问题
9、动态规划的问题与常用解决措施
问题 ： 动态规划在时间上比较快，但这是以牺牲空间为代价的，于是我们要设法解决空间溢出的问题
措施 ：（因题而异）
我们仅仅存储必不可少的内容
在某些情况下，用部分时间换取空间
在某些情况下，对于那些已用不到的数据，我们可以用数据覆盖数据，压缩空间
10、动态规划的常考类型
线性动划：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗
区域动规：石子合并，加分二叉树，统计单词个数，炮兵布阵
树形动归：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形
背包问题： 01背包，完全背包，分组背包，二维背包，装箱问题，挤牛奶（同济ACM 1132）
此上是根据百度词条整理、添加得到的