动态规划理论基础

动态规划直观理解

一个问题可以被拆分成多个步骤，并且每个步骤都有一个状态。后一个步骤可以由前一个步骤推导出来，那么就可以考虑使用动态规划。

解题步骤

五步曲

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

动态规划debug

在遍历的时候，打印 DP 数组。把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。