动态规划

概念

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划是把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解

分类

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。

举例：

线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；

区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；

树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；

背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等；

基本模型

(1)确定问题的决策对象。
(2)对决策过程划分阶段。
(3)对各阶段确定[状态变量]
(4)根据状态变量确定费用[函数]
(5)建立各阶段状态变量的转移过程，确定状态转移方程。