动态规划，千万不要被其高大上的名字吓坏了，我们可以用自己的理解去起一个自己喜欢的名字。
动态规划就是我们解决一个问题时，自底向上一步一步的推到我们问题。
也就是说，动态规划是一种 自底向上 的思维，当前阶段的状态会对以后阶段的状态有影响，一旦当前阶段的状态决定了，其前的状态就对其没有影响了，甚至对其以后的阶段的状态也没有影响了。
个人理解就是，动态规划就是一种自底向上的推导方法，一种自底向上的递推公式法。
动态规划，是指我们将一个大问题分解成几个小问题，单独解决各个小问题，小问题的最优解将是原始大问题的最优解。
如何确定一个问题就是DP问题呢？ DP问题主要是解决最值问题的，就看问题是否是求最值情况就好。
如何确定一个问题是使用DP方法解决的？ 要判断一个问题是否是 DP 问题，我们需要理解几个重要的概念：重叠子问题、最优子结构、无后效性。
- 重叠子问题：求解大问题时，我们拆分了多个小问题，小问题的求解是相同的。比如
Fibonacci，使用递归法求解n = 5时，需要求解两次n = 3的情况。那么这就是存在重叠子问题了。 - 最优子结构：大问题的最优解可以由小问题的最优解推出。
- 无后效性：如果确定了某一阶段的状态了，则在这一阶段以后的发展不受以前各阶段状态的影响。
所以要判断一个问题能否使用 DP 解决？就看这个问题能否拆分成多个小问题（重叠子问题），且满足无后效性和具有最优子结构。
- 判断是否是 DP 问题
- 确定子问题，也就是确定状态
- 明确DP table定义，构造状态转移方程，注意初始条件和边界情况
- 从子问题最优解中找出大问题的最优解
- 判断是否DP问题（求最值问题）
- 确定状态
- 状态转移方程（确定dp table）
- 注意初始条件和边界情况
- 解决顺序（自底向上、自顶向下）