贪心算法
贪心算法（Greedy Algorithm）是一类只看眼前的算法思想——它在每一步都做出「当前看来最好」的选择，不回退、不枚举所有可能，赌「局部最优叠加起来就是全局最优」。它不像 DP 那样穷举所有子问题再择优，而是一条路走到底：先按某种规则排序，再按某种规则逐个挑选。正因为省去了回溯与枚举，贪心通常极快（O(n log n) 的排序 + O(n) 的扫描），但它有一个致命前提——必须先证明「贪心选择性质」（局部最优能推出全局最优），否则它给出的可能只是看似合理却错误的解。
贪心的全部考点都源于一个心智模型：先设计贪心策略（怎么排序 + 怎么挑），再证明它对（否则换策略或上 DP）。由此衍生出三大主题：①贪心成立的两条件（贪心选择性质 + 最优子结构，缺一不可）；②正确性证明（交换论证、数学归纳、反证——不会证明就不敢用）；③经典贪心模型（活动选择 / 区间调度按结束时间排序、跳跃游戏按最远可达、分发糖果双向扫描、Huffman 编码优先队列合并、Dijkstra / Prim / Kruskal 本质都是贪心）。其中**「按结束时间排序选最多不重叠区间」是贪心的入门 Hello World，Huffman 编码是贪心 + 优先队列的典范，而找零问题**揭示了「标准币制贪心成立、非标准币制贪心失效」的典型反例——它正是贪心与 DP 的分水岭。
评价
优点
- 极快：排序 O(n log n) + 扫描 O(n) 是典型代价，远快于 DP 的 O(n²) 甚至 O(n³)——能用贪心就别用 DP
- 代码极简：核心逻辑往往就是「排序 + 一个 for 循环」，常数小、空间省（通常 O(1) 额外空间），写起来几乎不会错
- 决策确定性强：每步选择唯一确定（不回退不分支），实现可复用性高，常作为「优先尝试」的解法
- 是多个经典算法的内核：Dijkstra（最短路）、Prim / Kruskal（最小生成树）、Huffman 编码这些「大算法」本质上都是贪心策略的应用
缺点
- 不一定正确：贪心最大的硬伤——没有证明就贸然使用，可能得到错误解（典型反例：非标准币制找零、0-1 背包用单位价值贪心）
- 证明困难：贪心策略「看起来对」很容易，但严格证明「局部最优 ⇒ 全局最优」需要交换论证等技巧，是新手最容易翻车的地方
- 策略依赖排序键：贪心正确性高度依赖「按什么排序」，排序键选错（如活动选择按开始时间而非结束时间）整个策略就崩
- 无法回退：一旦做出选择就锁定，不能撤销——这是它区别于 DP（枚举所有可能择优）的根本原因
本叶地图
- 入门 —— 贪心核心思想、成立两条件、与 DP 的区别、贪心失效的典型反例
- 贪心策略与正确性证明 —— 策略设计（排序 + 选择）、证明方法（交换论证 / 归纳 / 反证）、贪心失效判断、贪心 vs DP 取舍
- 经典贪心问题 —— 活动选择 / 区间调度、跳跃游戏、分发糖果、Huffman 编码、Dijkstra / Prim / Kruskal 的贪心本质
- 参考 —— 成立条件、经典问题清单 + 代码、证明方法、贪心 vs DP 对比、易错点
交互演示
- 快速排序可视化演示 —— 贪心算法常依赖排序预处理，理解排序是理解贪心的前置基础