贪心算法在每一步都做出局部最优选择，希望这会导致全局最优。它简单快速，但仅当问题具有贪心选择性质和最优子结构时才正确。
核心思想
不要重新考虑过去的选择——提交最佳的即时选项并继续进行。
例子：标准硬币的硬币兑换
python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
这对美国硬币是最优的，但对于集合 {1, 3, 4} 失败，因为贪心对于 6 给出 4+1+1，而不是 3+3。
贪心何时有效
- 最优子结构： 最优解包含最优的子解。
- 贪心选择性质： 局部最优是全局最优的一部分。
有效的例子：Dijkstra、Kruskal/Prim (MST)、Huffman 编码、区间调度。
时间复杂度
通常很快——排序后通常为 O(n log n)。
陷阱
贪心不总是正确的。在相信它之前，请证明贪心选择性质或针对 brute-force/DP 基线进行测试。
为什么这很重要
当贪心适用时，它比 DP 或暴力法简单得多且速度快得多。
了解何时它是有效的——以及何时它悄悄地给出错误答案——是算法成熟度的标志。
许多基础图算法的核心是贪心的。