贪心算法（Greedy Algorithm）是信息学竞赛中一种非常重要的算法思想。它通常用于求解最优化问题：在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致全局最优解。
基本思想
贪心算法的核心可以概括为：“步步最优，最终全局最优？”
它不回溯，也不考虑未来的影响，只根据当前信息做出局部最优决策。与动态规划不同，贪心不保存所有状态，也不进行复杂的转移计算，因此实现简单、运行速度快。
但贪心算法并不总是能得到全局最优解，只有当问题具有贪心选择性质和最优子结构时，贪心策略才是正确的。
关键性质
一个问题能否用贪心算法求解，需要证明（或判断）它满足以下两个性质：
贪心选择性质
定义：一个问题如果可以通过一系列局部最优选择（贪心选择）得到全局最优解，则称它具有贪心选择性质。
也就是说，在求解过程中，不需要考虑子问题的解，只需做出当前看起来最好的选择，剩下的问题可以用同样的贪心策略解决。
最优子结构性质
定义：一个问题的最优解包含其子问题的最优解，则称它具有最优子结构。
贪心算法通常也是自顶向下的：先做出一次贪心选择，然后对剩下的子问题继续贪心。最优子结构保证子问题的最优解能够组合成原问题的最优解。
注意：动态规划也要求最优子结构，但贪心要求更强的“贪心选择性质”——即局部最优能导向全局最优，而不需要像 DP 那样考虑多种选择。
算法步骤
- 问题抽象：明确目标（最大化/最小化某个值）和约束条件。
- 确定贪心策略：即每一步的决策规则。例如“选择价值最大的”“选择结束时间最早的”“选择重量最轻的”等。
- 证明贪心策略的正确性（竞赛中通常靠直觉和常见模型，但严谨证明常用交换论证法或数学归纳法）。
- 实现：通常需要排序或使用优先队列，按贪心顺序处理。
经典贪心问题
活动安排问题（区间调度）
问题：有 n 个活动，每个活动有开始时间 s[i] 和结束时间 e[i]。选择尽可能多的互不重叠的活动（区间不重叠）。
贪心策略：按结束时间最早优先选择。每次选择结束时间最早且与已选活动不冲突的活动。
正确性：结束时间最早能为后续留下最多的时间。
区间选点问题
问题：给定 n 个闭区间，要求选最少的点，使得每个区间都至少包含一个点。
贪心策略：将区间按右端点升序排序，每次选择当前区间的右端点作为点，并去掉所有包含该点的区间。
代码：类似活动安排，只需在选择时跳过已覆盖的区间。
哈夫曼编码（Huffman Coding）
问题：给定字符频率，构造二叉树使得带权路径长度最小（常用于数据压缩）。
贪心策略：每次选择频率最小的两个节点合并，直到只剩一个节点。
实现：使用小根堆（优先队列）。
部分背包问题
问题：给定物品重量和价值，可分割（取部分），背包容量为 C，求最大价值。
贪心策略：按单位重量价值（价值/重量）降序排序，依次取满为止。
注意：0-1背包不能用贪心，但部分背包可以。
最小生成树（Kruskal、Prim）
Kruskal：按边权从小到大选择，若加入后不形成环则选择（并查集维护）。这是典型的贪心。
Prim：每次选择距离当前已选集合最近的点。
最短路径（Dijkstra）
Dijkstra 算法也是贪心：每次选择当前距离源点最近且未处理过的点进行松弛。
排队问题（最小化等待时间）
问题：n 个人接水，每个人需要时间 t[i]，求平均等待时间最小（或总等待时间最小）。
贪心策略：按接水时间从小到大排序。因为让耗时短的人先接水能减少后面人的等待。
证明：交换论证。
删数问题（使剩下的数最大/最小）
问题：给定一个数字串，删除 k 个数字，使得剩下的数字组成的数最大（或最小）。
贪心策略（最大）：从左到右，若发现当前数字比下一个数字小，则删除当前数字（因为高位尽量大）。重复 k 次。可以用单调栈优化 O(n)。
数列极差问题
问题：每次任取两个数，用它们的和或积替换，直至只剩一个数，求最终数的最大值和最小值。
贪心策略：
- 求最大值：每次取最小的两个数相加（保留大的数）。
- 求最小值：每次取最大的两个数相乘。
贪心算法与动态规划的关系
| 特性 | 贪心算法 | 动态规划 |
|---|---|---|
| 选择策略 | 只考虑当前最优，不回头 | 考虑所有可能的子问题选择 |
| 状态表示 | 通常不需要存储子问题解 | 需要表格存储状态 |
| 时间复杂度 | 通常 O(n log n) 或 O(n) | 往往 O(n²) 或更高 |
| 适用范围 | 满足贪心选择性质 | 满足最优子结构和重叠子问题 |
| 典型例子 | 活动安排、Dijkstra | 背包、最长公共子序列 |
如何区分：如果一个问题可以用贪心解决，那么用 DP 也能解，但贪心更快。如果找不出贪心策略，或者局部最优不一定全局最优，则考虑 DP。