浅谈动态规划
本篇是个人动态规划笔记。
应用动态规划方法：
- 刻画一个最优解的结构特征
- 递归地定义最优解的值
- 计算最优解的值，通常采用自底向上的方法
- 利用计算出的信息构造一个最优解
动态规划两种等价的实现方法：
- 带备忘的自顶向下法：此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，过程首先检查是否保存过此解。如果是，则直接返回保存的值，从而节省了计算时间，否则，按通常方式计算这个子问题。
- 自底向上法：这种方法一般需要恰当定义子问题『规模』的概念，使得任何子问题的求解都只依赖于『更小的』子问题的求解。因而我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所引来的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已求解完成。
适合动态规划求解的两个要素
最优子结构
如果一个问题的最优解包含其子问题的最优解没我们就称此问题具有最优子结构性质。
发掘此问题具有最优子结构性质的通用模式：
- 证明问题最优解的第一个组成部分是做出一个选择，做出这次选择产生一个或多个待解的子问题。
- 对于一个给定问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。
- 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，已经如何最好地刻画子问题空间。
- 利用『剪切-粘贴』(cut-and-paste) 技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。证明这一点是利用反证法：假定子问题的解不是其自身的最优解，那么我们就可以从原问题的解中『剪切』掉这些非最优解，将最优解『粘贴』进去，从而得到原问题一个最优的解，这与最初的解释原问题最优解的前提假设矛盾。
一个刻画子问题空间的好经验是：保持子问题空间尽可能简单，只在必要时才扩展它。
对于不同领域，最优子结构的不同体现在两个方面：
- 原问题的最优解中设计多少个子问题，以及
- 在确定最优解使用哪些子问题时，我们需要考察多少种选择
算法导论有两个实例值得一看。
重叠子问题
适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够『小』，即问题的递归算法会反复地求解相同的子问题，而不是一直声称新的子问题，即具有重复子问题性质。
实例
参考书籍：
《算法导论》