1. 基本思想： * 问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解； * 若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。 2. 使用条件：**可分为多个相关子问题，子问题的解被重复使用** * Optimal substructure（优化子结构）： ``` 一个问题的优化解包含了子问题的优化解 缩小子问题集合，只需那些优化问题中包含的子问题，降低实现复杂性 我们可以自下而上的 ``` * Subteties（重叠子问题）：在问题的求解过程中，很多子问题的解将被多次使用。 3.动态规划算法的设计步骤： * 分析优化解的结构 * 递归地定义最优解的代价 * 自底向上地计算优化解的代价保存之，并获取构造最优解的信息 * 根据构造最优解的信息构造优化解 4.动态规划特点: * 把原始问题划分成一系列子问题； * 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间 * 自底向上地计算。 * 整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）