动态规划

动态规划（英语：Dynamic programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划不是某一种具体的算法，而是一种算法思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

应用这种算法思想解决问题的可行性，对子问题与原问题的关系，以及子问题之间的关系这两方面有一些要求，它们分别对应了最优子结构和重复子问题。

最优子结构¶

最优子结构规定的是子问题与原问题的关系

动态规划要解决的都是一些问题的最优解，即从很多解决问题的方案中找到最优的一个。当我们在求一个问题最优解的时候，如果可以把这个问题分解成多个子问题，然后递归地找到每个子问题的最优解，最后通过一定的数学方法对各个子问题的最优解进行组合得出最终的结果。总结来说就是一个问题的最优解是由它的各个子问题的最优解决定的。

将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键。在解题中一般用状态转移方程描述这种组合。例如原问题的解为 \(f(n)\)，其中 \(f(n)\) 也叫状态。状态转移方程 \(f(n) = f(n - 1) + f(n - 2)\) 描述了一种原问题与子问题的组合关系。在原问题上有一些选择，不同选择可能对应不同的子问题或者不同的组合方式。例如

\[ f(n) = \left\{ \begin{array}{lr} f(n - 1) + f(n - 2) \qquad n = 2k \\ f(n - 1) \qquad\qquad\qquad n = 2k + 1 \\ \end{array} \right. \]

\(n=2k\) 和 \(n=2k+1\) 对应了原问题 \(n\) 上不同的选择，分别对应了不同的子问题和组合方式。

找到了最优子结构，也就能推导出一个状态转移方程 \(f(n)\)，通过这个状态转移方程，我们能很快的写出问题的递归实现方法。

重复子问题¶

重复子问题规定的是子问题与子问题的关系。

当我们在递归地寻找每个子问题的最优解的时候，有可能会重复地遇到一些更小的子问题，而且这些子问题会重叠地出现在子问题里，出现这样的情况，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多重复的计算。

重复子问题不是保证解的正确性必须的，但是如果递归求解子问题时，没有出现重复子问题，则没有必要用动态规划，直接普通的递归就可以了。

例如，斐波那契问题的状态转移方程 \(f(n)=f(n−1)+f(n−2)\)。在求 \(f(5)\) 时，需要先求子问题 \(f(4)\) 和 \(f(3)\)，得到结果后再组合成原问题 \(f(5)\) 的解。递归地求 \(f(4)\) 时，又要先求子问题 \(f(3)\) 和 \(f(2)\)，这里的 \(f(3)\) 与求 \(f(5)\) 时的子问题重复了。

问题核心¶

解决动态规划问题的核心：找出子问题及其子问题与原问题的关系

找到了子问题以及子问题与原问题的关系，就可以递归地求解子问题了。但重叠的子问题使得直接递归会有很多重复计算，于是就想到记忆化递归法：若能事先确定子问题的范围就可以建表存储子问题的答案。

动态规划算法中关于最优子结构和重复子问题的理解的关键点：

证明问题的方案中包含一种选择，选择之后留下一个或多个子问题；
设计子问题的递归描述方式；
证明对原问题的最优解包括了对所有子问题的最优解；
证明子问题是重叠的（这一步不是动态规划正确性必需的，但是如果子问题无重叠，则效率与一般递归是相同的）。

动态规划与其它算法的关系¶

分治¶

解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。然后不断地对它们递归地进行处理。

这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题，因为不断地对待排序的数组进行对半分的时候，两半边的数据并不重叠，分别解决左半边和右半边的两个子问题的时候，没有子问题重复出现，这是动态规划和分治的区别。

贪心¶

关于最优子结构
- 贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
- 动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解
关于子问题最优解组合成原问题最优解的组合方式
- 贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
- 动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案
结果正确性
- 贪心不能保证求得的最后解是最佳的，复杂度低
- 动态规划本质是穷举法，可以保证结果是最佳的，复杂度高


分治	动态规划	贪心
适用类型	通用	优化
子问题	每个都不同	有很多重复
最优子结构	没有要求	必须满足
子问题数	全部都要解	全部都要解