定义
动态规划（Dynamic Programming），简称 DP，是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法，先解决子问题，再由子问题的解得到原问题的解。这里的 Programming 并不是编程的意思，而是指一种 表格处理方法，即将每一步计算的结果存储在表格中，供随后的计算查询使用。
动态规划的核心思想：
- 问题拆解：将原问题拆解成子问题，每个求解子问题的过程构成一个阶段，完成一个阶段的求解再开始下一个阶段的求解。
- 存储子问题的解：子问题往往会被重复计算，因此记录下子问题的解，方便以后直接查询结果，而不是重新计算，空间换时间，降低时间复杂度。
特征
- 最优子结构：一个问题的最优解包含其子问题的最优解，即当前阶段做出的最优决策和剩余其他阶段的最优决策组成原问题的最优解。
- 重叠子问题：子问题会被多次求解（计算）。
- 无后效性：已经求解的子问题，不会影响到后续的决策。
基本思路
- 问题拆分：将原问题抽象为当前阶段要做的决策和上一阶段决策的结果，进而得出子问题
- 状态定义：描述一个阶段做了什么事，状态值就是每一个阶段决策的结果，也可以说是子问题的解
- 状态转移：根据前两步得出状态转移方程
- 初始化状态：即一些边界的处理，方便实现时直接调用状态转移方程
- 实现：遍历，根据状态转移方程计算各个阶段的状态