初识动态规划

动态规划

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

分类

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
举例：
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等；

算法思想

   1.将原问题分解为子问题
   2.确定状态
   3.确定初始态值
   4.确定状态转移方程

涉及的方面比较多，并且模型思想不可能用具体的算法表示，此处给出其两种应用的算法

示例--背包问题（背包动规）

http://www.cnblogs.com/liyuquan/p/7082235.html

示例--数字三角形（树形动规）

http://www.cnblogs.com/liyuquan/p/7082300.html

个人理解想必存在错误，欢迎指正