第九节 动态规划 - 1
简介
动态规划（Dynamic Programming, DP）及其解决的问题、根据其设计的算法及优化。
动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。
在 \(OI\) 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。
动态规划原理
能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
最优子结构
具有最优子结构也可能是适合用贪心的方法求解。
注意要确保我们考察了最优解中用到的所有子问题。
- 证明问题最优解的第一个组成部分是做出一个选择；
- 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
- 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
- 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。
要保持子问题空间尽量简单，只在必要时扩展。
最优子结构的不同体现在两个方面：
- 原问题的最优解中涉及多少个子问题；
- 确定最优解使用哪些子问题时，需要考察多少种选择。
子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。
无后效性
已经求解的子问题，不会再受到后续决策的影响。
子问题重叠
如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。
基本思路
对于一个能用动态规划解决的问题，一般采用如下思路解决：
- 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
- 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
- 按顺序求解每一个阶段的问题。