贪心算法-总览
思想描述
贪心算法（贪婪算法）是指在对问题进行求解时，在每一步都做出在当前看来是最好的选择，从而希望能够导致结果是最好或者最优的算法。贪心算法所得到的结果往往不是整体的最优解，而是局部的最优解。
贪心算法有两个基本性质，即贪心选择性质和最优子结构性质。贪心选择性质是贪心算法与动态规划算法的主要区别，其采用从顶向下、以迭代的方法做出相继选择。每做一次贪心选择，就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们需要证明每一步所作的贪心选择能最终得到问题的最优解。首先可以证明问题的一个整体最优解是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。最优子结构性质是指一个问题的最优解包含其子问题的最优解。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。
算法特征
贪心算法和动态规划算法有着很多类似的地方，将两者进行比较，可以更加深刻的理解贪心算法具有的特征。
最优解
- 贪心算法：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；
- 动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有的局部最优解
构造过程：
- 贪心算法：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下（自顶向下）遍历最优子树即可（通常这个“最优”都是基于当前情况下显而易见的“最优”）；这样的话，就不需要知道一个节点的所有子树情况，于是构不成一棵完整的树；
- 动态规划：动态规划则自底向上，从叶子向根，构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，最后得到一棵完整的树，并且最终选择其中的最优值作为自身的值，得到答案
复杂度：
- 贪心算法：根据以上两条可以知道，贪心算法不能保证求得的最后解是最佳的，一般复杂度低；
- 动态规划：动态规划本质是穷举法，可以保证结果是最佳的，复杂度高。