动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
基本思想
动态规划与分治法类似，其基本思想也是 将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，即 重复利用子问题的答案 这样就可以避免大量的重复计算，节省时间，这就是动态规划的优势。
设计步骤
基本步骤
-
划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
-
确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足 无后效性 。
-
确定决策并写出 状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
-
寻找边界条件：给出的状态转移方程是一个 递推式，需要一个递推的 终止条件或边界条件 。
简化
一般，只要 解决问题的阶段、状态 和 状态转移决策 确定了，就可以写出 状态转移方程（包括边界条件）。实际应用中可以按以下几个简化的步骤进行设计：
- 分析最优解的性质，并刻画其结构特征。
- 递归的定义最优解。
- 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
- 根据计算最优值时得到的信息，构造问题的最优解。
适用条件
-
最优化原理（最优子结构性质）：最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
-
无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
-
子问题的重叠性：动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于 解决冗余 ，这是动态规划算法的根本目的。动态规划实质上是一种以 空间换时间 的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
分类
动态规划一般可分为 线性动规，区域动规，树形动规，背包动规四类。
举例：
- 线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
- 区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
- 树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
- 背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等；