06 贪心算法：从直觉到证明的严格之路

贪心算法：从直觉到证明的严格之路

摘要

贪心算法是面试中最容易”猜对但说不清楚”的算法范式。很多人能感觉到”这道题应该用贪心”，但无法向面试官解释”为什么贪心是正确的”。本文从理论根基出发，深度解析贪心算法的两个核心性质（贪心选择性质与最优子结构），并系统介绍两种严格的正确性证明方法：交换论证法（Exchange Argument）和数学归纳法。理解了这两种证明方法，你在面试中面对任何贪心题，都能清晰地论证你的直觉是否正确——而不是靠运气猜对。

---

第 1 章 贪心算法的直觉与陷阱

1.1 什么是贪心算法

贪心算法的核心思想：在每一步决策中，选择在当前状态下看起来最好的选择，不回头，不考虑整体状态。

这个描述听起来很简单，甚至有点”不负责任”——你怎么能保证每次只看眼前的最优，最终也能达到全局最优？

答案是：不是所有问题都能用贪心，只有满足特定性质（贪心选择性质 + 最优子结构）的问题才能用贪心解决，而且你需要证明这两个性质成立。

1.2 贪心的经典反例

先看两个贪心会失败的例子，理解贪心的”边界”：

反例 1：0-1 背包问题

背包容量 10，物品列表（价值，重量）：(10, 6), (8, 5), (7, 5)

贪心策略（每次选”价值/重量”最高的）：先选 (10,6)，再选不了完整的 (8,5)（容量只剩 4），只能选……等等，拿不下去了，总价值 10。

最优解：(8,5) + (7,5) = 15，远超贪心的 10。

贪心失败的原因：0-1 背包中，选择一个物品会影响后续的选择空间（剩余容量减少），且不可撤销。局部最优（每步选最高性价比）不能保证全局最优。

反例 2：某些图的最短路问题

在有负权边的图中，Dijkstra 算法（一种贪心算法）会失败。因为贪心地选择”当前最短路径”的节点，可能后续遇到负权边让整体路径更短，但贪心已经”固化”了之前的选择。

贪心失败的根本原因：当前的最优选择”破坏了”未来最优选择的可能性，即局部最优不等于全局最优。

1.3 什么时候贪心是正确的

贪心正确的必要条件（两者缺一不可）：

条件 1：贪心选择性质（Greedy Choice Property）

存在一个最优解，使得它与贪心在第一步的选择相同。换句话说，总有一个最优解包含贪心的第一步选择，所以我们直接做贪心的选择不会损失最优性。

条件 2：最优子结构（Optimal Substructure）

做出贪心选择后，剩余的子问题仍然是原问题的子问题，且原问题的最优解 = 贪心的第一步选择 + 子问题的最优解。

直观理解：贪心选择性质保证”第一步贪心不会走错路”，最优子结构保证”走完第一步后，后面继续贪心就行”。两者合力保证”每步贪心 → 全局最优”。

---

第 2 章 交换论证法：最重要的贪心证明技术

2.1 交换论证法的框架

**交换论证法（Exchange Argument）**是证明贪心正确性的最强大工具，其框架如下：

1. 假设存在一个最优解 OPT，它与贪心策略给出的解 GRD 不完全相同（即在某步的选择上有差异）
2. 找到第一个差异点：在某步决策中，OPT 选择了 $x$，而 GRD 选择了 $y$（$x\ne y$）
3. 证明可以用 $y$ 替换 OPT 中的 $x$，得到新解 OPT’，使得 OPT’ 与 GRD 在这一步上相同，且 OPT’ 不比 OPT 更差（即 OPT’ 仍然是最优解）
4. 重复上述过程，逐步将 OPT 变成与 GRD 完全一致的解，同时保持最优性
5. 结论：GRD 本身就是一个最优解

注意：交换论证法不是说”能从 OPT 变到 GRD”就行，关键是”变换的每一步都不让解变差”——这才是贪心正确性的严格保证。

2.2 活动选择问题：经典交换论证

问题：有 $n$ 个活动，每个活动有开始时间 $s_i$ 和结束时间 $f_i$。同一时间只能参加一个活动（不能重叠）。选择最多的相互兼容的活动。

贪心策略：按结束时间从小到大排序，每次选择结束时间最早且与已选活动不冲突的活动。

直觉：选结束早的活动，给后续活动留下更多时间，从而能容纳更多活动。

交换论证：

假设最优解 OPT 包含活动序列 $a_1,a_2,...,a_k$（按结束时间排序），而贪心解 GRD 包含 $b_1,b_2,...,b_m$（也按结束时间排序，且 $b_1$ 是所有活动中结束时间最早的）。

如果 $a_1\ne b_1$：贪心选了 $b_1$（结束时间最早），而 OPT 选了 $a_1$（结束时间不早于 $b_1$，即 $f_{a_1}\ge f_{b_1}$）。

交换：在 OPT 中用 $b_1$ 替换 $a_1$，得到新解 OPT’。

• $b_1$ 是兼容的（与任何在 $b_1$ 结束后开始的活动都不冲突，因为 $f_{b_1}\le f_{a_1}$，OPT 中 $a_2,...,a_k$ 在 $a_1$ 结束后开始，同样在 $b_1$ 结束后开始）
• OPT’ 包含的活动数量与 OPT 相同（都是 $k$ 个）
• OPT’ 不比 OPT 差

因此存在一个最优解，它的第一个活动与贪心相同（都选 $b_1$）。对剩余子问题继续归纳，最终可以证明贪心解 GRD 的活动数量 $m=k$，即贪心解是最优的。

核心概念：交换不让解变差的条件

交换论证法的关键是证明”替换不让解变差”。通常需要利用贪心选择的某种单调性：

• 活动选择：贪心选结束时间最早的，替换后结束时间更早，给后续活动留下的时间只多不少
• 区间覆盖：贪心选覆盖最右的，替换后覆盖范围只增不减
• 最优编码（Huffman）：贪心合并频率最小的，可证明交换后编码代价不增

2.3 数学归纳法证明

另一种常见证明方式是数学归纳法，尤其适用于”问题规模递减”的贪心：

框架：

1. 基础情形：当问题规模为 1（或某个最小规模）时，贪心选择显然是最优的
2. 归纳假设：假设对规模 $<n$ 的问题，贪心策略是最优的
3. 归纳步骤：证明对规模为 $n$ 的问题，贪心的第一步选择与某个最优解一致（即贪心选择性质成立），然后剩余子问题规模 $<n$，由归纳假设知贪心继续最优

跳跃游戏（LeetCode 55）为例：

归纳假设：对于任何长度 $<n$ 的跳跃数组，“每次跳到当前可达的最远位置”的贪心策略是最优的（最少跳跃次数）。

基础情形：长度为 1 时，已在终点，跳 0 次，贪心最优。

归纳步骤（第 07 篇详细展开）：若长度为 $n$，贪心的第一跳选择能抵达的最远位置，此后剩余子问题长度 $<n$，由归纳假设继续最优。

---

第 3 章 贪心 vs 动态规划：从量变到质变

3.1 贪心是 DP 的特例

动态规划也要求”最优子结构”，但 DP 还允许子问题之间有重叠（用 memo 避免重复计算）。

贪心与 DP 的核心区别：

• DP：在每步决策时，需要考察所有可能的选择，每种选择都可能是最优的，需要通过子问题的最优值来确定。DP 看的是所有选择。
• 贪心：在每步决策时，只有一个选择是”最优的”（由贪心准则确定），无需考察其他选择。贪心只看一个选择。

贪心正是”每步只有一个最优选择”的 DP——当贪心选择性质成立时，DP 的最优值函数在每步只有一个转移方向，DP 表格被”压缩”为单次线性扫描，这就是贪心。

3.2 同一问题的 DP 解法 vs 贪心解法

最大连续子数组和（LeetCode 53）：

DP 解法（Kadane）：dp[i] = max(nums[i], dp[i-1] + nums[i])，每步有两个选择（重置 or 继承）。

贪心视角：当 dp[i-1] < 0 时，选择”重置”显然更优。所以其实每步的最优选择是唯一确定的（由 dp[i-1] 的正负决定），这使得 Kadane 同时具有 DP 和贪心的特征。

背包问题（0-1 背包）：

0-1 背包是纯 DP，不能用贪心（已见反例）。但分数背包（可以取物品的任意分数部分）可以用贪心：每次选单位重量价值最高的物品，直到背包装满。这是因为分数背包具有贪心选择性质（取性价比最高的物品总是最优的第一步），而 0-1 背包没有（选一个物品是全有全无的，影响后续选择空间）。

设计哲学：如何判断一道题能不能用贪心

经验性检验（不是严格证明）：

1. “后悔药”测试：如果能反悔（撤回之前的选择），能不能做得更好？如果能，贪心可能不行；如果不能，贪心可能有效。
2. 局部与全局一致性：局部最优选择是否能”不干扰”全局最优性？即当前的最优选择是否会关闭未来的最优选项？
3. 举反例：用小规模数据手工验证贪心策略，能举出反例则贪心不行。

但以上都只是启发式方法，严格证明才是最终标准。

3.3 贪心正确性证明的实际要求

在面试中，你通常不需要给出像学术论文那样严格的证明，但需要展示以下内容：

1. 说清楚贪心准则：我选择 [什么]，每次选择的依据是 [什么排序/比较规则]
2. 直觉解释：为什么这样选是合理的？（“因为选结束早的活动，给后续活动留出更多余地”）
3. 关键论点：给出交换论证的核心一步（“如果最优解第一步没选最早结束的活动，可以把它换成最早结束的，不会让解变差，因为……“）

这三点在面试中足以展示你对贪心算法的深度理解。

---

第 4 章 经典贪心场景分类

4.1 按排序+线性扫描

这是最常见的贪心模式：

1. 对输入按某个关键量排序
2. 线性扫描，每次做一个局部最优选择

典型例子：

• 活动选择（按结束时间排序）
• 区间不重叠（LeetCode 435，按结束时间排序）
• 最少箭头（LeetCode 452，按结束时间排序）
• 排队重建（LeetCode 406，按身高降序 + 前缀人数排序）

4.2 按可达范围维护

维护一个”当前可达的最右边界”，每步扩展这个边界：

• 跳跃游戏（LeetCode 55，55，45）：维护当前跳的最远位置
• 分糖果（LeetCode 455，Assign Cookies）：维护当前胃口可被满足的最小饼干

4.3 按差值/增量贪心

选择”当前增量最大的选项”，常见于利润类题目：

• 股票多次买卖（LeetCode 122）：每个正增量都累加
• 加油站（LeetCode 134）：维护当前段的净油量差值
• 分数背包：每次选单位价值最高的

4.4 构造类贪心

从结论出发，构造满足条件的序列：

• 柠檬水找零（LeetCode 860）：优先用大面值找零
• 队列重建（LeetCode 406）：按特定顺序插入，构造满足条件的序列

---

第 5 章 分数背包：教科书级的贪心正确性证明

5.1 问题定义

分数背包：背包容量 $W$，有 $n$ 个物品，第 $i$ 个物品有价值 $v_i$ 和重量 $w_i$。可以取每个物品的任意分数（0 到 1），取分数 $f_i$ 的代价是 $f_i\cdot w_i$，贡献是 $f_i\cdot v_i$。最大化总价值。

贪心策略：按单位重量价值 $v_i/w_i$ 降序排列，依次选取，直到背包装满。

5.2 严格证明

设贪心解为 GRD，假设存在另一个解 OPT 总价值更高。

设 GRD 中选的物品（及分数）为 $(f_1,f_2,...,f_n)$（已按 $v_i/w_i$ 降序排列），OPT 中为 $(g_1,g_2,...,g_n)$。

由于 GRD 是贪心策略，必然存在某个 $k$ 使得：

• 对 $i<k$：$f_i=1$（GRD 完全选取了前 $k-1$ 个物品）
• 对 $i=k$：$f_k=(W-{\sum }_{i<k}{w}_i)/w_k$（第 $k$ 个物品部分选取，装满背包）
• 对 $i>k$：$f_i=0$（背包已满）

价值差：GRD 与 OPT 的总价值差为：

$\text{GRD}-\text{OPT}={\sum }_{i=1}^n(f_i-g_i)\cdot v_i={\sum }_{i=1}^n(f_i-g_i)\cdot \frac{v_i}{w_i}\cdot w_i$

设 $r_i=v_i/w_i$（单位价值），GRD 的排序保证 $r_1\ge r_2\ge ...\ge r_n$。

注意到 ${\sum }_{i=1}^n(f_i-g_i)\cdot w_i=0$（GRD 和 OPT 都恰好装满背包，即总重量相同），这是一个约束。

利用这个约束和单调性 $r_1\ge r_2\ge ...$，可以证明（通过 Abel 求和或 rearrangement inequality）：

${\sum }_{i=1}^n(f_i-g_i)\cdot r_i\cdot w_i\ge 0$

即 $\text{GRD}\ge \text{OPT}$，矛盾（我们假设 OPT 更好）。

结论：不存在比 GRD 更好的解，GRD 是最优解。

这就是为什么分数背包可以贪心，而 0-1 背包不行：分数背包的可分性保证了”替换”操作的自由度，使得交换论证可以进行。

---

第 6 章 本文核心结论与后续预告

6.1 核心结论

1. 贪心正确性不是”感觉”：需要通过贪心选择性质和最优子结构来保证，不是所有局部最优就等于全局最优。

2. 交换论证法是最核心的证明工具：假设最优解与贪心不同，证明可以把最优解”交换”成贪心解而不变差，从而贪心本身就是最优解。

3. 贪心是 DP 的特例：当 DP 的每步只有唯一的最优选择时，DP 简化为贪心。

4. 四类贪心模式：排序+扫描、可达范围维护、差值/增量累积、构造类——绝大多数贪心面试题都属于这四类之一。

5. 面试中的证明要求：不需要写数学证明，但需要说清楚：贪心准则 + 直觉解释 + 关键交换论点。

6.2 后续安排

• 第 07 篇：跳跃游戏系列（LeetCode 55、45）——“可达范围维护”模式的最佳示范题，从数学归纳法视角彻底证明其正确性。

• 第 08 篇：区间调度贪心（LeetCode 435、452、56）——“排序+扫描”模式的三个变体，每道题用交换论证法完整推导。

• 第 09 篇：股票与序列贪心（LeetCode 122、134、860、406）——“差值累积”和”构造类”贪心的实战精讲，含一道容易错用贪心的陷阱题。