04 · 贪心算法（Greedy Algorithms）

📅 预计 90 分钟　|　⭐ 本章主题：每一步都选当下看起来最好的
📌 中英术语见文末

4.1 贪心思想

贪心 = 只管眼前，不求长远

想象你在登山，目标是山顶。贪心的做法是：每一步都朝当前最陡的上坡走，从不回头。这种"每步都选当下最优"的策略，就是贪心算法（greedy algorithm）的核心。

更生活化的例子：食堂打菜，菜盘子依次经过你面前，规则是"每人只能端走一份，端了就不能换"。贪心策略就是——只要面前这道菜比你手里的好，就换。它不看后面还会来什么菜。

贪心算法的一般形态：把问题分解成一系列局部决策，每一步都选择当前状态下的最优选项，做完一步就进入下一个状态，不回溯。它最大的特点是"短视"，所以：

好处：实现简单、速度快（通常 O(n log n) 或 O(n)）；
风险：不保证全局最优。登山时只挑当前最陡的坡，可能爬上一个小土包就下不来了。

# 贪心思想的雏形：从 1 开始，每次尽量多走，直到超过目标
# 这只是一个示意，真正的问题需要证明贪心正确
def greedy_sum(target):
    s = 0
    while s + 1 <= target:      # 每次只加 1（局部最优的最小步？）
        s += 1
    return s

print(greedy_sum(5))
# 输出: 5

⚠️ 常见错误

以为贪心对所有最优化问题都适用：贪心只在满足特定条件时才保证全局最优，很多问题贪心会给出错误答案（见 4.4 零钱反例）。
把"贪心"和"暴力枚举"混为一谈：贪心每步只做一次选择、不回退；枚举是把所有可能都试一遍，完全不同。
不证明就下结论：写出来很快，但"为什么这样最优"必须用贪心选择性质论证，否则就是猜。

4.2 贪心的两个要素 ⭐

什么时候敢用贪心？

一个最优化问题能用贪心解决，需要同时满足两个性质：

贪心选择性质（greedy-choice property）：可以通过做出一系列局部最优的选择来构造全局最优解。也就是说，存在一个最优解，它的第一步就是贪心选择——选完这一步，剩下的子问题仍可用贪心继续。
最优子结构（optimal substructure）：问题的最优解包含其子问题的最优解。大问题拆成子问题后，只要子问题各自最优，合起来就是大问题最优。

判断流程（画决策树很直观）：

每一步选完，剩下的问题还是同一类、规模更小的问题吗？→ 对应最优子结构；
存在一个最优解以"当前贪心选择"为第一步吗？→ 对应贪心选择性质。

验证方法：先用小数据手算一遍，如果贪心答案和穷举最优答案完全一致，说明很可能正确；再尝试构造反例——找一个贪心会错的数据。找不到反例 + 能证明两步性质，才敢放心用。

💡 记忆口诀：贪心两件套——"第一步敢不敢这么选"（贪心选择性质）+"子问题最优拼起来就是全局最优"（最优子结构）。

⚠️ 常见错误

只有最优子结构，没有贪心选择性质：最优子结构是贪心、分治、动态规划共有的前提，单独有它不足以证明贪心。
用"经验上感觉对"代替证明：贪心正确性必须论证或找反例，不能靠直觉。
不检查局部最优组合后是否仍整体最优：局部最优的叠加有时并不等于全局最优。

4.3 活动选择问题 ⭐

一个会议室，怎么安排最多的活动？

问题：有一间会议室，n 个活动各占一个区间 [start, end)，一个时间只能开一个活动，求最多能安排几个活动。

贪心策略：每次选"结束时间最早"且与已选不冲突的活动。直觉：结束越早，给后面留的时间越多。

def activity_selection(start, end):
    """start、end 已按结束时间升序排列"""
    n = len(start)
    count = 1                          # 第一个活动必选
    last_end = end[0]
    for i in range(1, n):
        if start[i] >= last_end:       # 与上一个已选活动不冲突
            count += 1
            last_end = end[i]
    return count

# 活动区间：(1,2) (3,4) (0,6) (5,7) (8,9) (5,9)，已按结束时间排序
start = [1, 3, 0, 5, 8, 5]
end   = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, end))
# 输出: 4  → 选 (1,2)、(3,4)、(5,7)、(8,9)

为什么贪心正确：设最优解中结束最早的活动为 e1。按"结束时间最早"贪心选出的活动 g1 结束时间 ≤ e1，用 g1 替换 e1 不改变活动个数，还让剩余时间更宽松。于是存在一个最优解以 g1 为第一步，剩余子问题同构——贪心选择性质 + 最优子结构同时满足。

复杂度：需要先按结束时间排序 O(n log n)，然后一趟 O(n)，总 O(n log n)。

# 未排序时的完整流程：先排序再贪心
activities = [(1, 2), (0, 6), (3, 4), (5, 7), (8, 9), (5, 9)]
activities.sort(key=lambda x: x[1])        # 按结束时间排序
sel = []
last_end = -1
for s, e in activities:
    if s >= last_end:
        sel.append((s, e))
        last_end = e
print(sel)
# 输出: [(1, 2), (3, 4), (5, 7), (8, 9)]

⚠️ 常见错误

按"开始时间最早"或"持续时间最短"贪心：这两个策略对活动选择都不保证最优，必须按结束时间最早。
忘排序就贪心：核心是"结束最早的先处理"，必须先排序。
边界判断写反：区间不冲突的条件是 start[i] >= last_end，写成 > 会漏掉"无缝衔接"的活动。

4.4 零钱问题

贪心不一定对，要看币制

问题：给定若干面额的硬币，用最少硬币凑出金额 M。经典做法是"从最大面额开始，能塞多少塞多少"：

def coin_change_greedy(coins, amount):
    coins = sorted(coins, reverse=True)   # 从大到小
    total = 0
    for c in coins:
        total += amount // c              # 尽量多用大面额
        amount %= c
        if amount == 0:
            break
    return total if amount == 0 else -1   # -1 表示凑不出来

print(coin_change_greedy([25, 10, 5, 1], 63))
# 输出: 6  → 25×2 + 10×1 + 1×3 = 6 枚

但对某些币制，贪心是错的。反例：币值 {1, 5, 11}，凑 15：

贪心：先拿 11，剩 4 → 再拿 4 个 1，共 5 枚；
最优：3 个 5，共 3 枚。

贪心被 11 带偏了。结论：

当币制满足某种"规范"条件（如人民币的 1/5/10 递进），贪心正确；
币制任意时，贪心不保证最优，需要用动态规划（第 05 章）保证正确。

coins = [1, 5, 11]
amount = 15
coins.sort(reverse=True)
used, rem = 0, amount
for c in coins:
    used += rem // c
    rem %= c
print(f"贪心: {used} 枚")      # 输出: 贪心: 5 枚（错误）
# 正确答案是 3 枚：5 + 5 + 5

💡 记忆口诀：零钱贪心要看币制——规范币制贪心对，任意币制会翻车，翻车就上动态规划。

⚠️ 常见错误

默认贪心永远正确：{1, 5, 11} 凑 15 是教科书反例，务必记住。
没检查是否恰好凑满：贪心可能凑不出精确金额，要处理返回 -1 的情形。
把零钱问题写成"排序后能拿就拿"就完事：要能回答"什么时候贪心正确"，才算真懂。

4.5 区间调度

最少移除多少区间，让剩下不重叠

问题变体：给定若干区间，移除最少数量的区间，使剩余区间互不重叠；等价于"保留最多的互不重叠区间"。和活动选择本质相同——保留尽可能多的不重叠区间，答案就是 n 减保留数。

def erase_overlap(intervals):
    intervals.sort(key=lambda x: x[1])     # 按结束时间排序
    keep = 0
    last_end = float("-inf")
    for s, e in intervals:
        if s >= last_end:                 # 不重叠就保留
            keep += 1
            last_end = e
    return len(intervals) - keep          # 要移除的数量

print(erase_overlap([[1, 2], [2, 3], [3, 4], [1, 3]]))
# 输出: 1  → 移除 [1,3]，剩三个互不重叠

同族问题：合并区间（把所有重叠区间并成一个大区间）也用贪心——按起点排序后，一趟合并。

def merge_intervals(intervals):
    intervals.sort()                      # 按起点排序
    res = []
    for s, e in intervals:
        if res and s <= res[-1][1]:       # 与当前结果最后一个重叠
            res[-1][1] = max(res[-1][1], e)  # 扩展右端点
        else:
            res.append([s, e])
    return res

print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))
# 输出: [[1, 6], [8, 10], [15, 18]]

⚠️ 常见错误

合并区间按结束排序：合并必须先按起点排序，否则相邻区间找不对。
把"移除最少"和"保留最多"搞混：两者互补，答案相差常数，别算错。
边界"重叠"定义不一致：[1,2] 和 [2,3] 是接壤不重叠（s >= last_end 放行）；要包含端点需统一约定。

4.6 哈夫曼编码 ⭐

压缩数据：给高频字符发短码，低频字符发长码

背景：ASCII 里每个字符固定占 8 位。如果一篇文档里 e 出现几百万次、z 出现几次，让高频字符的编码更短、低频的更长，总长度就能大幅压缩。

关键约束是前缀码（prefix code）：任何一个字符的编码，都不能是另一个字符编码的前缀——否则解码时会歧义。哈夫曼编码（Huffman coding）用贪心构造一棵最省总长度的前缀树：

把所有字符按频率建一个最小堆；
每轮弹出频率最小的两个，合并成一个"新节点"（频率相加），重新入堆；
重复直到堆里只剩一个节点，就是哈夫曼树；
从根到叶子，左分支记 0、右分支记 1，得到每个字符的编码。

贪心点在于"每次合并当前频率最小的两个"——让频率低的字符待在树更深处（编码更长），频率高的字符待在更浅处（编码更短）。

import heapq

def huffman(freq):
    heap = [[w, [sym, ""]] for sym, w in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)          # 频率最小的
        hi = heapq.heappop(heap)          # 频率次小的
        for pair in lo[1:]:
            pair[1] = "0" + pair[1]
        for pair in hi[1:]:
            pair[1] = "1" + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(heap)[1:])

freq = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}
print(huffman(freq))
# 输出: [['a', '0'], ['b', '101'], ['c', '100'], ['d', '111'], ['e', '1101'], ['f', '1100']]
# 哈夫曼编码本身不唯一，但平均码长总是最优

这段代码里 heap 每个元素是 [权重, [符号, 编码], ...]，合并时给两组的编码分别加上 0 和 1 前缀。注意哈夫曼编码不唯一（并列频率的合并顺序不同结果不同），但平均码长最优。

复杂度：每轮从堆里取最小 O(log n)，共 n-1 轮，总 O(n log n)。

⚠️ 常见错误

说编码结果唯一：哈夫曼编码不唯一，但任何一棵哈夫曼树的平均码长都最优。
破坏前缀码约束：直接按频率排序取前几位做编码可能产生前缀冲突，必须通过构造树保证前缀性。
堆里存了 (权重, 符号) 元组就够了：不行，合并后要带整棵子树，通常存 [权重, 节点列表]。

4.7 贪心 vs 动态规划

长得像，但一个"不回看"，一个"回头看"

贪心与动态规划（DP）都要求最优子结构，都常用于最优化问题，但决策方式本质不同：

对比项	贪心	动态规划
决策依据	只看当前局部最优	综合比较所有子问题解
是否回溯	否，一路向前	否，但会重复利用子问题解
需要重叠子问题	不依赖	依赖（否则没有 DP 的价值）
正确性	需额外证明贪心选择性质	靠状态转移保证全局最优
典型复杂度	O(n) ~ O(n log n)	看状态数 × 转移成本
失败情形	局部最优 ≠ 全局最优	不适用的问题也能硬写但低效

同一个问题两种解法的对比——零钱问题：

贪心（币制规范时）：从大到小，O(k) 时间，但任意币制可能错；
动态规划：枚举所有凑法取最小，正确性有保证，但复杂度更高（O(amount × 币种数)）。

# 零钱问题的动态规划解法（正确性有保证，见第 05 章详述）
def coin_change_dp(coins, amount):
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for m in range(1, amount + 1):
        for c in coins:
            if c <= m:
                dp[m] = min(dp[m], dp[m - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(coin_change_dp([1, 5, 11], 15))
# 输出: 3  → 5 + 5 + 5（贪心给 5，是错误的）

选择指引：能证明贪心性质 → 用贪心（快）；证明不了、但问题有最优子结构和重叠子问题 → 用动态规划（稳）。分治则是"子问题不重叠"的那一类，与 DP 不冲突。

💡 记忆口诀：贪心是"走一步看一步"，DP 是"把每一步的最优都记下来拼起来"；证明不了贪心就上 DP。

⚠️ 常见错误

贪心错了也不换 DP：遇到反例（如 {1,5,11} 凑 15）就应改用 DP，别硬撑。
认为 DP 一定比贪心慢很多：DP 慢在状态多，但很多问题状态空间可控，是保证正确性的可靠手段。
分治、贪心、DP 三者边界混淆：子问题独立不重叠 → 分治；每步局部最优且可证 → 贪心；子问题重叠且要比较多种选择 → DP。

🧠 记忆口诀

贪心一句话：走一步看一步，选当下最优，不回头。
两个要素：贪心选择性质（第一步敢这么选）+ 最优子结构（子问题最优拼全局最优）。
活动选择：按结束时间最早排，能排就排。
零钱反例：{1,5,11} 凑 15，贪心 5 枚、最优 3 枚。
区间调度：保留最多不重叠 = 结束最早优先；合并区间按起点排。
哈夫曼：最小堆每次合并两个最小频率，左 0 右 1 造前缀码。
贪心 vs DP：能证明用贪心，证明不了用 DP。

📌 中英术语表（本讲）

中文	English	说明
贪心算法	greedy algorithm	每步选当前局部最优
贪心选择性质	greedy-choice property	存在最优解以贪心选择为第一步
最优子结构	optimal substructure	最优解包含子问题最优解
局部最优	local optimum	当前步骤下的最优
全局最优	global optimum	整个问题的最优
活动选择问题	activity-selection problem	最多互不重叠活动
零钱问题	coin change problem	最少硬币凑出金额
反例	counterexample	推翻策略错误的例子
区间调度	interval scheduling	区间不重叠的取舍
前缀码	prefix code	任意码不是另一码的前缀
哈夫曼编码	Huffman coding	频率高的码短，频率低的码长
最小堆	min-heap	每次可取最小元素的结构
回溯	backtrack	撤销之前的决策
动态规划	dynamic programming	用子问题最优解递推全局最优

⭐ 本章考点清单

贪心思想：每步局部最优、不回溯、不保证全局最优
贪心的两个性质：贪心选择性质 + 最优子结构
活动选择：按结束时间最早排序，O(n log n)
零钱问题反例 {1,5,11} 凑 15：贪心 5 枚 vs 最优 3 枚
区间调度：移除最少 = 保留最多不重叠
合并区间：按起点排序一趟合并
哈夫曼编码：最小堆每次合并两个最小频率，前缀码，O(n log n)
哈夫曼编码不唯一但平均码长最优
贪心 vs 动态规划对比：正确性保证、复杂度、适用条件
判断流程：可证贪心则用贪心，否则用 DP