贪心算法

1 简介

贪心算法（英语：greedy algorithm），是用计算机来模拟一个“贪心”的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

2 适用范围

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

3 证明方法

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。

1. 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
2. 归纳法：先算出边界情况（例如$n=1$ ）的最优解$F_1$，然后再证明：对于每个$n$，$F_{n+1}$ 都可以由$F_n$推导出结果。

4 与动态规划的区别

• 贪心算法：对每个子问题的解决方案都做出选择，不能回退。
• 动态规划：则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

5 解题

5.1 常见题型

在提高组难度以下的题目中，最常见的贪心有两种。

• 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
• 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）

二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。

5.2 排序解法

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

5.3 后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

5.4 注意

预处理：在处理数组前，统计一遍信息（如频率、个数、第一次出现位置、最后一次出现位置等）可以使题目难度大幅降低。

6 参考

• OI-wiki

7 题目列表

试题链接	解题链接	备注
Leetcode 455. 分发饼干	-	排序
Leetcode 135. 分发糖果	-	两次遍历
Leetcode 435. 无重叠区间	-	区间问题
Leetcode 605. 种花问题	-	-
452. 用最少数量的箭引爆气球	-	和435类似
763. 划分字母区间	-	预处理
122. 买卖股票的最佳时机 II	-	累加所有的上坡
406. 根据身高重建队列	解法	二维排序，插入
665. 非递减数列	数学规律解法	逆序对，数学规律，未用贪心