本讲定位：五级最后一个知识块，也是最容易”以为会了其实没会”的一讲。贪心的代码往往只有几行，难点全在**“凭什么这样贪是对的”。官方大纲专门点名了「最优子结构」，说明要求学生理解贪心成立的条件**，而不只是背几个模板。
对应官方大纲：五级知识块 8「贪心算法」——贪心算法的相关概念、最优子结构。
前置知识：排序、五级第 05 讲（二分答案里的 check 常常是贪心）、五级第 07 讲（分治）。
代码说明：本讲代码均已用 g++ 11.5 编译运行验证；反例部分与暴力枚举对拍确认。
贪心算法（Greedy）：每一步都选择”当前看起来最好”的选项，不回头、不反悔，期望最终得到全局最优解。
生活例子：从家到学校，每个路口都选”看起来最近”的方向走。有时能走到最短路，有时会绕远——这就是贪心的特点：简单、快，但不一定对。
$$ \boxed{\textbf{贪心的核心问题不是“怎么写”，而是“凭什么对”}} $$
定义：问题的最优解，包含其子问题的最优解。
通俗说：把大问题的最优解拆开，里面每一块也必须是对应子问题的最优解。
例：从 A 到 C 的最短路经过 B，那么”A 到 B 这一段”必须是 A 到 B 的最短路。（否则换成更短的那段，整体会更短，矛盾。）
⚠️ 最优子结构是贪心和动态规划（六级）的共同前提——两者都靠它。光有最优子结构不够，还需要下面这条。
定义：每一步的局部最优选择，能够导向全局最优解。
这是贪心和 DP 的分水岭：
| 最优子结构 | 贪心选择性质 | |
|---|---|---|
| 贪心 | ✅ 需要 | ✅ 需要 |
| 动态规划 | ✅ 需要 | ❌ 不需要（所以要枚举所有决策） |
📌 一句话总结：
这是六级学 DP 时最重要的一个铺垫，务必讲清楚。