动态规划

动态规划(dynamic programming)是求解决策过程(decision process)最优化的数学方法。一般分为：

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

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

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

背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等； 动态规划的特点： ------把原始问题划分成一系列子问题（与分治法相同） ------求解每个子问题仅一次，并将其结果保存在一个表中，以后用到的时候直接取 ------自底向上地计算（分治法自顶向下，没有考虑子问题重叠） 适用范围： ------优化问题：可分为多个相关子问题，子问题的解被重复使用 使用动态规划的条件 ------优化子结构（保证动态规划的正确性）：当一个问题的优化解包含了子问题的优化解时，我们说这个问题具有优化子结构。如果不具有优化子结构，保存结果就没有意义了，反而浪费了空间。 ------重叠子问题：在问题的求解过程中，很多子问题的解将被多次使用 动态规划算法的设计步骤： ------分析优化解的结构 ------递归地定义最优解的代价 ------自底向上地计算优化解的代价保存之，并获取构造最优解的信息 ------根据构造最优解的信息构造优化解 动态规划的核心是状态和状态转移方程。