适用的问题类型
一般是求最值类型的问题可以尝试应用动态规划方法来解决。
解题步骤：明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。
关键
状态和选择
-状态可以是变化的东西。
比如背包问题里：「背包的容量」和「可选择的物品数组」
走楼梯问题：当前所处的层数。
股票里：天数，交易次数，持有不持有（状态机）
-选择：在当前状态，可以做一个操作，变成下一个状态。
背包问题的装进背包和不装进背包。
股票：买入，卖出，不操作。
问题所具备的特点
- 最优子结构。
大问题能够分解成小问题，小问题也是最优化的问题。 - 重叠子问题。
小问题之间存在重叠。存在着问题之间互相利用，一个问题计算许多次等现象。这个小问题有可能是规模小，也有可能是结构小。 - 状态转移方程。（数学归纳法）
问题之间存在关联。能从小问题推导出大问题。这些不同规模的问题代表着当前所处不同的状态，不同的状态之间存在状态转移方程，即递推公式。
