动态规划和贪婪算法总结

PS：鉴于经验比较少，此文所写理论占多，待以后补充

动态规划和贪婪算法是一对孪生兄弟，但是动态规划是哥哥，因为动态规划可以解决的问题贪婪算法不一定能解决，反之，贪婪算法可行的动态规划一样可行，但是相对时间复杂度会更大

问题性质

动态规划问题具有两个性质：最优子结构(optimal substructure)和重叠子问题(overlapping subproblems)

而贪婪算法问题具有两个性质：最优子结构和贪婪选择性质(greedy-choice property)

你会发现两者都有最优子结构，最优子结构指的是原问题的最优解包含相关子问题的最优解，即原问题的最优解依赖于子问题的最优解

动态规划能适用的问题一定会有重叠子问题的性质，如果一个问题只有最优子结构(e.g.Quicksort)，那么它没有必要用动态规划，因为动态规划本来就是让这些重叠的子问题只执行一次而让程序得到优化的一种算法技巧

贪心算法也不具有重叠子问题性质，反而具备贪婪选择性质：局部最优解即是全局最优解的一部分，通过贪心选择，我们留下一个子问题，依次根据贪心选择得到局部解，最终组合在一起就是全局最优解，整个过程中没有重叠子问题，每个子问题都是相异的，也正因此，子问题个数相比动态规划往往更少，时间复杂度更小(e.g.prim or kruskal algorithm of MST)

步骤

发现最优子结构的通用模式如下：

说明问题的解是由做出选择构成的，这些选择将会产生子问题
假设该选择会得到最优解，而不关注怎么得到该选择
根据该选择，确定会产生哪些子问题和如何刻画子问题空间
通过“cut-and-paste”方法证明：作为最优解的一部分，子问题的解对于它本身就是最优的，即证明子问题的解确实是最优解

最后一个步骤是一般用反证法证明：

假设有比子问题解更优的解，将子问题解cut下来，将该更优解paste进某关系式(步骤2和3得到)得到矛盾，从而得出子问题解为最优解

另外，子问题空间的刻画应当尽可能的小，即可以用一维解决的没必要用二维，也就是说可能需要空间压缩

最优子结构还可以得到：

原问题最优解使用了哪些子问题
决定哪些子问题用于最优解有多少个选择

实际上这个和动态规划的时间复杂度的两个组成因素有关：子问题数量和每个子问题需要考察多少选择

比如Rot-Cutting问题中，子问题数量为$\Theta(n)$,而每个子问题最多考察n个选择，所以是时间复杂度为$O(n^2)$

然后就可以动态规划和贪心选择的抉择：

动态规划：

描述最优解的结构（根据题意定义dp[…]并描述其表示什么)
基于子问题最优解递归定义最优解的值（根据最优子结构得到状态转移方程）
计算最优解的值（相比recursion&memoization用iterating&bottom-up更为方便）
根据计算得到的信息构造最优解（一般可以通过回溯法将最优解输出）

贪心选择：

将最优化问题转化为：做出选择然后留下一个子问题去解决
证明贪心选择总是可以得到原问题的最优解
证明最优子结构通过证明：做出贪心选择后留下的子问题的最优解与贪心选择组合在一起即可得到原问题的最优解

贪心选择的证明一般也可通过“cut-and-paste”方法证明：但是与动态规划不同，是通过直接“cut”不包含贪心选择的最优解的其他选择并且“paste”贪心选择后依然可以得到最优解或更优解（一般如果是更优解，会与假设矛盾而弹回最优解），这样贪心选择就可以得到原问题的最优解，通过贪心选择将子问题空间缩小了