动态规划

简介

一些情况下，复杂的问题可以拆分成简单的子问题。

如果一个问题的最优解可以由一个或多个子问题的最优解推出，就可以根据推导关系把这些子问题组织成有递推关系的多个阶段。

规定每一个子问题都对应一个状态，并且规定子问题的最优解即是状态值。那么问题的最优解由子问题的最优解推出，就等价于状态可以转移出新的状态。

以目前所有状态为一个阶段，那么所有状态及所有可行动作组合出的所有的新的最优状态就是下一个阶段。这样一来，就形成了有递推关系的多个阶段。所求答案往往是某个阶段的某个状态的值。

性质

显然，想要动态规划，至少应该满足：

1. 最优子结构：每个问题可以拆为分子问题，而问题的最优解由子问题的最优解组合而成。
2. 无后效性：状态只受之前阶段的状态影响。

此外，如果要使动态规划比直接做更优，还需要：

3. 子问题重叠：子问题有重复计算的情况，所以可以在动态规划时存储状态值（子问题的解）来节省计算。

数学

设 $dp_t(s)$ 表示到达阶段 $t$ 的状态 $s$ 时，能够得到的最优值。处于状态 $s$ 时，可以选择动作 $a\in\mathcal A_t(s)$，获得收益 $r_t(s,a)$，并转移到下一阶段的状态 $f_t(s,a)$。

对于下一阶段的状态 $s'$，它的最优值来自所有能够转移到 $s'$ 的状态和动作：

$$dp_{t+1}(s') =\operatorname*{opt} \left\{ dp_t(s)+r_t(s,a)\ \middle|\ f_t(s,a)=s' \right\}.$$

其中，$\operatorname{opt}$ 根据问题的目标取 $\max$ 或 $\min$。实际编程时，通常从初始状态开始，枚举每个动作，用 $dp_t(s)+r_t(s,a)$ 去更新下一状态 $dp_{t+1}(s')$。