动态规划

什么时候可以用到动态规划？

1. 最优子结构 用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。
2. 重叠子问题 如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。

如何使用动态规划：

1. 找出状态转移方程
2. 找出初始状态
3. 考虑要不要用滚动数组

算法-动态规划 Dynamic Programming--从菜鸟到老鸟