举个例子，如下图所示，原问题 $S = \lbrace a_1, a_2, a_3, a_4 \rbrace$ ，在 $a_1$ 步我们通过贪心选择选出一个当前最优解之后，问题就转换为求解子问题 $S_{\text{子问题}} = \lbrace a_2, a_3, a_4 \rbrace$ 。如果原问题 $S$ 的最优解可以由「第 $a_1$ 步通过贪心选择的局部最优解」和「 $S_{\text{子问题}}$ 的最优解」构成，则说明该问题满足最优子结构性质。

也就是说，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。

在做了贪心选择后，满足最优子结构性质的原问题可以分解成规模更小的类似子问题来解决，并且可以通过贪心选择和子问题的最优解推导出问题的最优解。

反之，如果不能利用子问题的最优解推导出整个问题的最优解，那么这种问题就不具有最优子结构。

1.3 贪心算法正确性的证明

贪心算法最难的部分不在于问题的求解，而在于是正确性的证明。我们常用的证明方法有「数学归纳法」和「交换论证法」。

数学归纳法：先计算出边界情况（例如 $n = 1$ ）的最优解，然后再证明对于每个 $n$ ， $F_{n + 1}$ 都可以由 $F_n$ 推导出。
交换论证法：从最优解出发，在保证全局最优不变的前提下，如果交换方案中任意两个元素 / 相邻的两个元素后，答案不会变得更好，则可以推定目前的解是最优解。

判断一个问题是否通过贪心算法求解，是需要进行严格的数学证明的。但是在日常写题或者算法面试中，不太会要求大家去证明贪心算法的正确性。

所以，当我们想要判断一个问题是否通过贪心算法求解时，我们可以：

凭直觉：如果感觉这道题可以通过「贪心算法」去做，就尝试找到局部最优解，再推导出全局最优解。
举反例：尝试一下，举出反例。也就是说找出一个局部最优解推不出全局最优解的例子，或者找出一个替换当前子问题的最优解，可以得到更优解的例子。如果举不出反例，大概率这道题是可以通过贪心算法求解的。

3. 贪心算法三步走

转换问题：将优化问题转换为具有贪心选择性质的问题，即先做出选择，再解决剩下的一个子问题。
贪心选择性质：根据题意选择一种度量标准，制定贪心策略，选取当前状态下「最好 / 最优选择」，从而得到局部最优解。
最优子结构性质：根据上一步制定的贪心策略，将贪心选择的局部最优解和子问题的最优解合并起来，得到原问题的最优解。

4. 贪心算法的应用

4.1 分发饼干

4.1.1 题目链接

455. 分发饼干 - 力扣

4.1.2 题目大意

描述：一位很棒的家长为孩子们分发饼干。对于每个孩子 $i$ ，都有一个胃口值 $g[i]$ ，即每个小孩希望得到饼干的最小尺寸值。对于每块饼干 $j$ ，都有一个尺寸值 $s[j]$ 。只有当 $s[j] > g[i]$ 时，我们才能将饼干 $j$ 分配给孩子 $i$ 。每个孩子最多只能给一块饼干。

现在给定代表所有孩子胃口值的数组 $g$ 和代表所有饼干尺寸的数组 $j$ 。

要求：尽可能满足越多数量的孩子，并求出这个最大数值。

说明：

$1 \le g.length \le 3 * 10^4$ 。
$0 \le s.length \le 3 * 10^4$ 。
$1 \le g[i], s[j] \le 2^{31} - 1$ 。

示例：

示例 1：

输入：g = [1,2,3], s = [1,1]
输出：1
解释：你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1, 2, 3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以应该输出 1。

示例 2：

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1, 2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2。

4.1.3 解题思路

思路 1：贪心算法

为了尽可能的满⾜更多的⼩孩，而且一块饼干不能掰成两半，所以我们应该尽量让胃口小的孩子吃小块饼干，这样胃口大的孩子才有大块饼干吃。

所以，从贪心算法的角度来考虑，我们应该按照孩子的胃口从小到大对数组 $g$ 进行排序，然后按照饼干的尺寸大小从小到大对数组 $s$ 进行排序，并且对于每个孩子，应该选择满足这个孩子的胃口且尺寸最小的饼干。

下面我们使用贪心算法三步走的方法解决这道题。

转换问题：将原问题转变为，当胃口最小的孩子选择完满足这个孩子的胃口且尺寸最小的饼干之后，再解决剩下孩子的选择问题（子问题）。
贪心选择性质：对于当前孩子，用尺寸尽可能小的饼干满足这个孩子的胃口。
最优子结构性质：在上面的贪心策略下，当前孩子的贪心选择 + 剩下孩子的子问题最优解，就是全局最优解。也就是说在贪心选择的方案下，能够使得满足胃口的孩子数量达到最大。

使用贪心算法的代码解决步骤描述如下：

对数组 $g$ 、 $s$ 进行从小到大排序，使用变量 $index\_g$ 和 $index\_s$ 分别指向 $g$ 、 $s$ 初始位置，使用变量 $res$ 保存结果，初始化为 $0$ 。
对比每个元素 $g[index\_g]$ $g [in d e x_g]$ 和 $s[index\_s]$ $s [in d e x_s]$ ：
1. 如果 $g[index\_g] \le s[index\_s]$ ，说明当前饼干满足当前孩子胃口，则答案数量加 $1$ ，并且向右移动 $index\_g$ 和 $index\_s$ 。
2. 如果 $g[index\_g] > s[index\_s]$ ，说明当前饼干无法满足当前孩子胃口，则向右移动 $index_s$ ，判断下一块饼干是否可以满足当前孩子胃口。
遍历完输出答案 $res$ 。

思路 1：代码

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        index_g, index_s = 0, 0
        res = 0
        while index_g < len(g) and index_s < len(s):
            if g[index_g] <= s[index_s]:
                res += 1
                index_g += 1
                index_s += 1
            else:
                index_s += 1   

        return res

思路 1：复杂度分析

时间复杂度： $O(m \times \log m + n \times \log n)$ ，其中 $m$ 和 $n$ 分别是数组 $g$ 和 $s$ 的长度。
空间复杂度： $O(\log m + \log n)$ 。

4.2 无重叠区间

4.2.1 题目链接

435. 无重叠区间 - 力扣

4.2.2 题目大意

描述：给定一个区间的集合 $intervals$ ，其中 $intervals[i] = [starti, endi]$ 。从集合中移除部分区间，使得剩下的区间互不重叠。

要求：返回需要移除区间的最小数量。

说明：

$1 \le intervals.length \le 10^5$ 。
$intervals[i].length == 2$ 。
$-5 * 10^4 \le starti < endi \le 5 * 10^4$ 。

示例：

示例 1：

输入：intervals = [[1,2],[2,3],[3,4],[1,3]]
输出：1
解释：移除 [1,3] 后，剩下的区间没有重叠。

示例 2：

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

4.2.3 解题思路

思路 1：贪心算法

这道题我们可以转换一下思路。原题要求保证移除区间最少，使得剩下的区间互不重叠。换个角度就是：「如何使得剩下互不重叠区间的数目最多」。那么答案就变为了：「总区间个数 - 不重叠区间的最多个数」。我们的问题也变成了求所有区间中不重叠区间的最多个数。

从贪心算法的角度来考虑，我们应该将区间按照结束时间排序。每次选择结束时间最早的区间，然后再在剩下的时间内选出最多的区间。

我们用贪心三部曲来解决这道题。

转换问题：将原问题转变为，当选择结束时间最早的区间之后，再在剩下的时间内选出最多的区间（子问题）。
贪心选择性质：每次选择时，选择结束时间最早的区间。这样选出来的区间一定是原问题最优解的区间之一。
最优子结构性质：在上面的贪心策略下，贪心选择当前时间最早的区间 + 剩下的时间内选出最多区间的子问题最优解，就是全局最优解。也就是说在贪心选择的方案下，能够使所有区间中不重叠区间的个数最多。

使用贪心算法的代码解决步骤描述如下：

将区间集合按照结束坐标升序排列，然后维护两个变量，一个是当前不重叠区间的结束时间 $end\_pos$ ，另一个是不重叠区间的个数 $count$ 。初始情况下，结束坐标 $end\_pos$ 为第一个区间的结束坐标， $count$ 为 $1$ 。
依次遍历每段区间。对于每段区间： $intervals[i]$ $in t er v a l s [i]$ ：
1. 如果 $end\_pos \le intervals[i][0]$ ，即 $end\_pos$ 小于等于区间起始位置，则说明出现了不重叠区间，令不重叠区间数 $count$ 加 $1$ ， $end\_pos$ 更新为新区间的结束位置。
最终返回「总区间个数 - 不重叠区间的最多个数」即 $len(intervals) - count$ 作为答案。

思路 1：代码

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        end_pos = intervals[0][1]
        count = 1
        for i in range(1, len(intervals)):
            if end_pos <= intervals[i][0]:
                count += 1
                end_pos = intervals[i][1]

        return len(intervals) - count

思路 1：复杂度分析

时间复杂度： $O(n \times \log n)$ ，其中 $n$ 是区间的数量。
空间复杂度： $O(\log n)$ 。

练习题目

参考资料

【博文】贪心 - OI Wiki
【博文】贪心算法 | 算法吧
【博文】贪心算法理论基础 - Carl - 代码随想录
【博文】小白带你学贪心算法（Greedy Algorithm) - 知乎
【书籍】算法导论第三版（中文版）- 殷建平等译
【书籍】ACM-ICPC 程序设计系列 - 算法设计与实现 - 陈宇吴昊主编