贪心算法

概述

贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。它不像动态规划算法那样计算更大的格局。

1. 根据实际问题，选取一个度量标准，然后按照这种标准对 n 个输入进行排序，并按次序一次输入一个量
2. 如果输入和当前已构成的部分最优解不能产生下一个可行解，则不把此输入加入到部分解中，否则将当前输入合并到解中从而得到新的部分最优解
3. 这一过程一直持续知道 n 个输入都被处理完毕，计入最优解中的输入子集构成最优解

这种能够得到某种意义下的最优解的分级处理方法被称为贪心算法

并不是所有问题都可以贪心解决的, 而是本身是符合贪心的定义的, 才能用贪心解

这么说有点抽象，来举一个例子：

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

再举一个例子如果是 有一堆盒子，你有一个背包体积为 n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。

什么时候可以使用贪心算法?

为什么这种问题局部的最优可以逐渐扩展到全局的最优?

很多同学做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。

说实话贪心算法并没有固定的套路

所以唯一的难点就是如何通过局部最优，推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？

不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

有同学问了如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧

可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。

一般数学证明有如下两种方法：

• 数学归纳法
• 反证法

看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。

面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了

举一个不太恰当的例子：我要用一下 1+1 = 2，但我要先证明 1+1 为什么等于 2。严谨是严谨了，但没必要。

虽然这个例子很极端，但可以表达这么个意思：刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心

例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！

所以这也是为什么很多同学通过（accept）了贪心的题目，但都不知道自己用了贪心算法，因为贪心有时候就是常识性的推导，所以会认为本应该就这么做！

那么刷题的时候什么时候真的需要数学推导呢？

例如这道题目：链表：环找到了，那入口呢？ (opens new window)，这道题不用数学推导一下，就找不出环的起始位置，想试一下就不知道怎么试，这种题目确实需要数学简单推导一下。

和动态规划的区别

都是一个推导的过程

感觉一起处理吧? 还是太难区分贪心和动归

贪心算法 在每一步总是做出在当前看来最好的选择。

「贪心算法」 和 「动态规划」、「回溯搜索」 算法一样，完成一件事情，是 分步决策 的；

「贪心算法」 在每一步总是做出在当前看来最好的选择，我是这样理解 「最好」 这两个字的意思：

「最好」 的意思往往根据题目而来，可能是 「最小」，也可能是 「最大」；

贪心算法和动态规划相比，它既不看前面（也就是说它不需要从前面的状态转移过来），也不看后面（无后效性，后面的选择不会对前面的选择有影响），因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的；

这道题 「贪心」 的地方在于，对于 「今天的股价 - 昨天的股价」，得到的结果有 3 种可能：① 正数，② 0，③负数。贪心算法的决策是： 只加正数 。

TODO

散落四处的贪心算法处理, 打一下 tag, 归类处理一下

一般的解题步骤

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。

做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。

想想看能不能找到反例, 其实还挺难想的

背包问题

各种大米，小米，糯米，黄米，等重量 20kg 以内，价格最高

商品按价格排序，先装价格最高的，装完再装价格次高的，次次高的

最小生成树

Prim 算法

Kruskal 算法

最少硬币找零问题

最少硬币找零问题也能用贪心算法解决。大部分情况下的结果是最优的，不过对有些面额而言，结果不会是最优的。

function MinCoinChange(coins){ 
  var coins = coins; //{1} 

  this.makeChange = function(amount) { 
    var change = [], 
        total = 0; 
    for (var i=coins.length; i>=0; i--){ //{2} 
      var coin = coins[i]; 
      while (total + coin <= amount) { //{3} 
        change.push(coin);           //{4} 
        total += coin;               //{5} 
      } 
    } 
    return change; 
  }; 
} 

对每个面额（行{2}——从大到小），把它的值和 total 相加后，total 需要小于 amount（行 {3}）。我们会将当前面额 coin 添加到结果中（行{4}），也会将它和 total 相加（行{5}）

如你所见，这个解法很简单。从最大面额的硬币开始，拿尽可能多的这种硬币找零。当无法再拿更多这种价值的硬币时，开始拿第二大价值的硬币，依次继续。

直接法 + 模拟法

605. 种花问题

好几题都好像回溯, 但是其实不是

需要好好品一下回溯和暴力的区别了

376. 摆动序列

53. 最大子数组和

55. 跳跃游戏

45. 跳跃游戏 II

区间问题

在遍历的过程中, 不断更新能达到的最远边界, 所以跳跃问题也可以归到这一类

55. 跳跃游戏

45. 跳跃游戏 II