动态规划

概念

动态规划(Dynamic programming, DP)是一种将复杂的原问题分解成相对简单的子问题的解决复杂问题的方法。

特征

可以使用动态规划方法解决的问题都具有重叠子问题、最优化子结构和无后效性三大特征，这类问题一般是求最值的问题，可以使用穷举法解决。

重叠子问题

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

无后效性

即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

最优化子结构

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

如何写出状态转移方程

1. 确定base case，即最初时的情况。

2. 确定状态，即变量。

3. 确定选择，即导致状态变化的行为。

4. 确定dp数组的定义。

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)