动态规划（Dynamic Programming，简称 DP），如果某一问题有很多重叠子问题，使用动态规划是最有效的。

和贪心的区别在于：

• 动态规划中每一个状态一定是由上一个状态推导出来的
• 贪心没有状态推导，而是从局部直接选最优的，