原理：
什么是贪心
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
贪心的套路（什么时候用贪心）
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优，推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？
靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢？
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
模板：
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。
题目实战：
① 简单题：
贪心，正向思路，反向思路——2022年8月13日15:32:40 - 分发饼干 - 力扣（LeetCode）
贪心——2022年8月13日16:41:37 - 最大子数组和 - 力扣（LeetCode）
贪心——2022年8月14日19:44:21 - 柠檬水找零 - 力扣（LeetCode）
② 中等题：
1）序列问题：
贪心——2022年8月13日16:16:55 - 摆动序列 - 力扣（LeetCode）
贪心，递归——2022年8月15日20:50:36 - 单调递增的数字 - 力扣（LeetCode）
2）股票问题：
贪心——2022年8月13日17:10:58 - 买卖股票的最佳时机 II - 力扣（LeetCode）
贪心，递归——2022年8月15日20:50:36 - 单调递增的数字 - 力扣（LeetCode）
3）两个维度权衡问题：
遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
如果两个维度一起考虑一定会顾此失彼。
两次贪心——2022年8月14日19:26:41 - 分发糖果 - 力扣（LeetCode）
二维贪心——2022年8月14日21:35:49 - 根据身高重建队列 - 力扣（LeetCode）
③ 难题：
1）区间问题：
贪心——2022年8月13日17:26:53 - 跳跃游戏 - 力扣（LeetCode）
贪心——2022年8月13日18:03:07 - 跳跃游戏 II - 力扣（LeetCode）
贪心——2022年8月13日21:17:45 - K 次取反后最大化的数组和 - 力扣（LeetCode）
贪心——2022年8月15日00:50:37 - 用最少数量的箭引爆气球 - 力扣（LeetCode）
无重叠区间：如果两个区间有重叠，应该保留结尾小的，结合图示很容易想到。
贪心，区间贪心——2022年8月15日13:34:39 - 无重叠区间 - 力扣（LeetCode）
贪心，脑筋急转弯，哈希——2022年8月15日18:09:05 - 划分字母区间 - 力扣（LeetCode）
贪心，二维排序，区间问题——2022年8月15日18:25:28 - 合并区间 - 力扣（LeetCode）
2）其他：
贪心——2022年8月14日16:42:41 - 加油站 - 力扣（LeetCode）
贪心，后序遍历，递归——2022年8月15日21:53:07 - 监控二叉树 - 力扣（LeetCode）
总结：
贪心没有套路，说白了就是常识性推导加上举反例。
最好用的策略就是举反例，如果发现是想不到反例，那这时候就可以试一试贪心吧。
虽然贪心是常识，有些常识并不容易，甚至很难！
参考链接：
|