动态规划（dp）学习笔记_dp算法如何证明最优性

1、动态规划原理

适合应用动态规划方法求解的问题具有两个要素：最优子结构和子问题重叠。

1.1、最优子结构

所谓问题具有最优子结构性质，就是问题的最优解包含其子问题的最优解。这个要素可以帮助我们确定一个问题是否可以应用动态规划或者贪心策略解决。而发掘一个问题的最优子结构性质的过程，可以遵循以下通用模式：

1. 证明问题最优解的第一个组成部分是做出一个选择；
2. 对一个给定问题，假定在其第一步选择中，已知哪种选择能得到最优解（不关心如何得到这种选择）；
3. 对这一给定的最优解选择，确定会产生哪些子问题，以及如何最好地刻画这个子问题空间；
4. 利用剪切粘贴方法，证明每个子问题的解在作为构成原问题的最优解的组成部分时，这个解就是子问题本身的最优解。

刻画子问题空间时，最好保持子问题空间尽可能简单。

在动态规划方法中，通常自底向上使用最优子结构，也就是先求出子问题最优解并记录下来，再求原问题的最优解。贪心策略与之相对，先求一个局部最优解，再求解随之产生的子问题，从而不必求解所有的子问题。

使用动态规划需要注意问题是否具有最优子结构性质。例如有向图的无权最短路径问题与无权最长路径问题，前者有最优子结构，但后者作为NP完全问题是没有最优子结构的。这是由于最长简单子路径问题是相关的，一个子问题使用过的顶点是无法被另一个子问题使用的；而最短简单子路径问题之间不共享资源，是无关的(independent)，因为假如有一个顶点同时出现在两条最短子路径上࿰