动态规划
能用动态规划解决的问题需要具备三个特征：
- 最优子结构：问题的最优解包含子问题的最优解，或后面阶段的状态可以通常前面状态推导出来
- 无后效性：某阶段状态一旦确定，就不受之后阶段的决策影响
- 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态
能用动态规划解决的问题通常也能使用回溯算法解决。在使用回溯算法解决问题的时候，画出递归树，检查递归树中是否存在很多重复节点。如果是，那该问题往往可以用动态规划进行优化。
动态规划的状态压缩
动态规划问题通常需要额外开辟一个n^2的空间记录状态，但实际需要用的状态往往只有n，因此可以通过一定方法削减额外空间开辟。