introduce
动态规划是通过组合子问题的解来解决整个问题，不同与分治算法，动态规划的子问题不是相互独立的， 动态规划通过对每个子子问题只计算一次来优化计算过程。
动态规划一般用于最优化问题求解.
一般步骤
- 描述最优解结构
- 递归定义最优化解的值, 定义递归式(最重要的一部)
- 按自底向上的方式计算最优解
- 构造一个最优解(一般不需要，或第三部已经保留了过程)
能应用动态规划的两个主要特征
- 问题包含最优子结构,父问题的最优解需要子问题的最优解
- 子问题重叠，应用动态规划可以提高性能
动态规划的变形: 备忘
自顶向下的计算策略.
使用低效但是容易理解的递归算法，同时对子问题解进行缓存。