【理论】贪心算法
什么是贪心
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，只要每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果有一堆盒子，有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
贪心的套路（什么时候用贪心）
贪心算法并没有固定的套路。唯一的难点就是如何通过局部最优，推出整体最优。 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
Q: 如何验证可不可以用贪心算法呢？
A: 最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
贪心一般解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了，我们平时在做贪心类的题目时，如果按照这四步去思考，真是有点“鸡肋”。做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。
贪心经典题目
贪心简单题
以下三道题目就是简单题，大家会发现贪心感觉就是常识。是的，如下三道题目，就是靠常识，但我都具体分析了局部最优是什么，全局最优是什么，贪心也要贪的有理有据！
贪心中等题
贪心中等题，靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处。
贪心解决股票问题
大家都知道股票系列问题是动规的专长，其实用贪心也可以解决，而且还不止就这两道题目，但这两道比较典型，我就拿来单独说一说
- 贪心算法：买卖股票的最佳时机II(opens new window)
- 贪心算法：买卖股票的最佳时机含手续费 (opens new window)本题使用贪心算法比较绕，建议后面学习动态规划章节的时候，理解动规就好
两个维度权衡问题
在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。
在讲解本题的过程中，还强调了编程语言的重要性，模拟插队的时候，使用C++中的list（链表）替代了vector(动态数组)，效率会高很多。
所以在贪心算法：根据身高重建队列（续集） (opens new window)详细讲解了，为什么用list（链表）更快！
大家也要掌握自己所用的编程语言，理解其内部实现机制，这样才能写出高效的算法！
贪心难题
这里的题目如果没有接触过，其实是很难想到的，甚至接触过，也一时想不出来，所以题目不要做一遍，要多练！
贪心解决区间问题
关于区间问题，大家应该印象深刻，有一周我们专门讲解的区间问题，各种覆盖各种去重。
- 贪心算法：跳跃游戏(opens new window)
- 贪心算法：跳跃游戏II(opens new window)
- 贪心算法：用最少数量的箭引爆气球(opens new window)
- 贪心算法：无重叠区间(opens new window)
- 贪心算法：划分字母区间(opens new window)
- 贪心算法：合并区间(opens new window)
其他难题
贪心算法：最大子序和 (opens new window)其实是动态规划的题目，但贪心性能更优，很多同学也是第一次发现贪心能比动规更优的题目。
贪心算法：加油站 (opens new window)可能以为是一道模拟题，但就算模拟其实也不简单，需要把while用的很娴熟。但其实是可以使用贪心给时间复杂度降低一个数量级。
最后贪心系列压轴题目贪心算法：我要监控二叉树！ (opens new window)，不仅贪心的思路不好想，而且需要对二叉树的操作特别娴熟，这就是典型的交叉类难题了。
贪心每周总结
周总结里会对每周的题目中大家的疑问、相关难点或者笔误之类的进行复盘和总结。
如果大家发现文章哪里有问题，那么在周总结里或者文章评论区一定进行了修正，保证不会因为我的笔误或者理解问题而误导大家。
所以周总结一定要看！
- 本周小结！（贪心算法系列一）(opens new window)
- 本周小结！（贪心算法系列二）(opens new window)
- 本周小结！（贪心算法系列三）(opens new window)
- 本周小结！（贪心算法系列四）(opens new window)
总结
版权声明：
作者：Zhang, Hongxing
链接：http://zhx.info/archives/699
来源：张鸿兴的学习历程
文章版权归作者所有，未经允许请勿转载。