动态规划原理

如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有 最优子结构 性质。一个问题是否能够应用动态规划算法，考察它是否具有最优子结构性质是一个好线索。但是要注意的是，在用子问题最优解构造原问题最优解事，我们必须保证考察了所有可能的子问题。

实际上在发掘最优子结构性质的过程中，遵循了如下的通用模式：

1. 证明问题最优解的第一个组成部分是做出一个选择。
2. 对于一个给定的问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。
3. 给定可获得最优解的选择后，确定这次选择会产生哪些子问题，以及如果最好的刻画子问题空间。
4. 利用“剪切-粘帖”技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。使用反证法证明这一点。

除此之外，一个刻画子问题空间的好经验是：保持子问题空间尽可能简单，只在必要时才扩展它。

对于不同问题领域，最优子结构的不同体现在两个方面： 1. 原问题的最优解中涉及多少个子问题 2. 在确定最优解使用哪些子问题时，我们需要考察多少种选择。

我们还可以用子问题的总数和每个子问题需要考察多少选择这两个因素的乘积来粗略的分析动态规划算法的运行时间。这与子问题图很类似。

一般在求解过程中，采用自底向上的方法使用最优子结构。先求出子问题的最优解，然后求原问题的最优解。

动态规划方法求解的最优化问题应该具备的第二个性质是重叠子问题性质。即在递归算法中会反复地求解相同的子问题，而不是一直生成新的子问题。如果递归算法反复求解相同的子问题，我们就称最优化问题具有*重叠子问题*性质。

动态规划对每个子问题只求解一次，然后将其解保存在一个表中，当再次需要这个解时直接查表，节省了大量的时间。凡是一个问题的自然递归算法中反复出现相同的子问题时，动态规划算法都能极大的提高效率。

从实际考虑，通常将每个子问题所做的选择存在一个表中，这样能通过将其递归展开来重构最优解。

除了自底向上，还可以是使用自顶向下的策略，能够达到和自底向上相似的效率。思路就是对自然但低效的递归算法加入备忘机制。当递归调用过程中第一次遇到子问题时，计算其解并存入备忘表。之后每次再遇到相同的问题，只是简单的查表并返回。

通常情况下，如果每个子问题都需要求解一次，自底向上的方法比自顶向下的方法更快。但是如果某些子问题不需要求解的时候，备忘法的优势就体现出来了，因为它只会求解必要的子问题。

综上所述，动态规划的关键是先考察一个问题是否适合用动态规划算法求解，也就是说是否具有*最优子结构*和*重叠子问题*性质。如果适合，那么就根据最优子结构来定义一个递归的求最优解的方法，并使用自顶向下或自底向上的方法对其求解、保存最优解的选择，最后根据保存的最优选择来重构最优解。