1. 算法思想
动态规划建立在分治思想的基础上，在利用分治算法求解问题时，可能遇到子问题之间互相关联，会造成重复求解，从而影响算法效率。那么对于这类具有优化子结构和子问题重叠性的优化问题时，可以根据优化子问题设计数据结构和i问题的求解次序，从规模最小的子问题开始自底向上地计算每个子问题的解，保证每个子问题被求解一次；将求得的子问题的解和构造最优解所需要的信息存储在数据结构中；再根据最优解的构造信息得到优化问题的最优解。
2. 前提条件
应用动态规划解决问题需要原问题具有优化子结构以及子问题重叠性的特点：
优化子结构 ：优化问题的解可以通过一系列子问题的解构造得到，称该问题具有优化子结构；
子问题重叠性 ：若根据分治算法求解该优化问题的解，将导致某些子问题被重复求解，则称该问题具有子问题重叠性；
3. 设计步骤
- 分析问题的优化解；
- 递归地定义最优解地代价；
- 自底向上地计算优化解地代价并保存之，并获取构造最优解的信息；
- 根据构造最优解的信息构造最优解。
4. 典型问题
- 斐波那契数列求解
- 最长公共子序列
- 矩阵链乘法
