动态规划

动态规划前提：

1、最优化原理：最优解的子问题也是最优，具有最优子结构。

2、无后效性：只与当前状态有关。

3、有重叠子问题：这不是必须的，但若子问题不能被多次使用，使用动态规划就不具备优势。