1. 从一道"找零钱"问题说起：贪心算法到底在贪什么
很多人第一次接触贪心算法，都是从"找零钱"这道经典题开始的。给定面额为1元、5元、10元、20元、50元、100元的纸币，要求用最少的张数凑出某个金额。绝大多数人的直觉是：先用最大面额去凑，凑不下了再换小面额。这个直觉，就是贪心算法的雏形。
但这里有个容易被忽略的细节：为什么找零钱用贪心是对的？如果面额换成1元、3元、4元，要凑6元，贪心会先拿4元，剩下2元只能用两个1元，总共3张；而最优解是两张3元。贪心在这里失效了。所以贪心算法从来不是"无脑选最大"，它成立的前提是问题本身具备某种结构性质，通常叫贪心选择性质和最优子结构。
我在Day_28这天专门花时间把贪心算法从头梳理了一遍，起因是前面几天做动态规划（DP）时，发现自己有个思维惯性：遇到最优化问题就想上DP，结果有些题用DP写出来又长又慢，而贪心几行就搞定。这让我意识到，贪心和DP不是替代关系，而是针对不同问题结构的两种武器。搞清楚"什么时候该贪、什么时候不能贪"，比背几道题的模板重要得多。
这篇内容适合两类人：一类是刚学完排序、递归，准备进入算法进阶的初学者；另一类是像我这样，DP写顺手了反而对贪心生疏、需要重新校准判断标准的人。我会把贪心的核心判断逻辑、典型题型、证明思路，以及我自己踩过的坑，完整地摊开讲一遍。核心关键词就三个：贪心选择、局部最优、反例验证。
2. 贪心算法的判断标准：局部最优为什么能推到全局最优
2.1 贪心的本质是一次"不可回退"的决策序列
贪心算法的工作方式，可以类比成走迷宫时每一步都选当前看起来最近的那条路，而且选了就不回头。这一点是它和DP最根本的区别。DP会保留所有子问题的解，最后综合出一个全局最优；贪心则是走一步算一步，做完当前决策就把它固定下来，后续不再修改。
正因为"不可回退"，贪心算法通常非常高效，时间复杂度往往就是排序的O(n log n)加上一次线性扫描O(n)。但代价是：一旦某一步贪错了，整个结果就错了，没有补救机会。所以判断一道题能不能用贪心，本质上是在问：我每一步都选当前最优，最后会不会自动收敛到全局最优？
这个问题没有万能公式，但有两个可操作的判断工具，我在实践中反复用。
2.2 两个判断工具：贪心选择性质与最优子结构
贪心选择性质指的是：问题的全局最优解，可以通过一系列局部最优的选择达到。换句话说，你不需要"预知未来"，只看当前信息做的最优选择，一定属于某个全局最优解的一部分。
最优子结构指的是：一个问题的最优解包含其子问题的最优解。这个性质和DP是共用的，DP也要求最优子结构。区别在于，DP还需要重叠子问题（所以要用记忆化或递推表），而贪心不需要，它只沿着一条决策路径往下走。
我自己的判断流程是这样的：
- 先确认问题有最优子结构（大问题的最优解由小问题的最优解拼成）。
- 再尝试构造一个贪心策略，比如"按结束时间排序""按单位价值排序"。
- 用交换论证法或反例法验证这个策略是否成立。
交换论证法的思路是：假设存在一个最优解，它和贪心解在第一个不同的决策点上选择不同，然后证明把最优解的那个选择换成贪心的选择，结果不会变差。如果能证明，贪心就成立。这个证明方法听起来抽象，但用起来很直接，下面结合具体题型讲。
2.3 一个反直觉的结论：贪心不是"简单题"，而是"结构题"
很多人有个误解，觉得贪心是入门算法，比DP简单。我的体会恰恰相反：贪心的代码往往很短，但想出正确的贪心策略、并证明它成立，难度经常高于写一个DP。DP有相对固定的套路（定义状态、写转移方程、定边界），而贪心每道题的策略都不一样，非常依赖对问题结构的洞察。
举个我踩过的坑。有一道区间调度题，我第一反应是按区间开始时间排序，然后依次选不重叠的区间。结果提交后部分用例错了。正确做法是按区间结束时间排序。为什么？因为结束越早，留给后面区间的时间就越多，这是一个"越早腾出资源越好"的贪心。按开始时间排序则完全没有这个保证。这个例子说明，贪心策略的细节（按哪个字段排序、升序还是降序）往往决定成败，而这些细节必须靠对问题的理解去推，不能靠感觉。
3. 四类高频贪心题型：从区间调度到 Huffman 合并
3.1 区间调度类：按结束时间排序的经典套路
区间调度是贪心最经典的战场。问题描述通常是：给定一堆区间，选出尽可能多的互不重叠的区间。策略是按结束时间升序排序，然后依次选取与上一个已选区间不重叠的区间。
为什么按结束时间？我用交换论证解释一下。假设最优解选的第一个区间是A，贪心选的第一个区间是B（B的结束时间最早）。因为B结束最早，所以B的结束时间不晚于A。那么把最优解里的A换成B，剩下的区间仍然能和B兼容（因为B结束更早，留给后面的空间更大）。所以贪心解不会比最优解差。这个论证链条清晰，是理解区间调度的关键。
代码实现上，排序后维护一个"上一个选中区间的结束时间"变量即可：
def max_non_overlapping(intervals): if not intervals: return 0 intervals.sort(key=lambda x: x[1]) # 按结束时间升序 count = 1 last_end = intervals[0][1] for start, end in intervals[1:]: if start >= last_end: # 不重叠 count += 1 last_end = end return count这里有个边界细节：start >= last_end还是start > last_end，取决于题目对"重叠"的定义。如果区间是闭区间且端点相接算重叠，就要用严格大于。我在做题时因为没看清这个定义，白白错了一次，后来养成了先确认端点语义的习惯。
3.2 跳跃游戏类：维护"最远可达"边界
跳跃游戏是另一类高频题。给定一个数组，每个元素表示从该位置最多能跳多远，问能否到达最后一个位置。贪心策略是：维护当前能到达的最远位置，遍历过程中不断更新它。
def can_jump(nums): farthest = 0 for i, jump in enumerate(nums): if i > farthest: # 当前位置已经不可达 return False farthest = max(farthest, i + jump) return True这道题的精髓在于，你不需要关心"具体怎么跳"，只需要关心"最远能到哪"。这是一种典型的贪心思维：把问题从"求具体方案"降维成"求某个边界值"。我一开始总想着记录跳跃路径，写得很复杂，后来发现只要维护一个边界变量就够了。这个思路的转变，是我学贪心过程中最有价值的一次认知升级。
3.3 分发类问题：排序后双指针贪心
分发问题（比如分发糖果、分发饼干）通常的策略是：先排序，然后用双指针或贪心地满足最小需求。以分发饼干为例，每个孩子有一个胃口值，每块饼干有一个尺寸，只有饼干尺寸大于等于胃口值才能满足。问最多能满足多少孩子。
策略是：孩子按胃口升序、饼干按尺寸升序，然后双指针扫描，能用小饼干满足小胃口就用小的，把大饼干留给大胃口。
def find_content_children(greed, cookies): greed.sort() cookies.sort() child = cookie = 0 while child < len(greed) and cookie < len(cookies): if cookies[cookie] >= greed[child]: child += 1 # 这个孩子被满足 cookie += 1 return child这里的贪心逻辑是"不浪费"：能用刚好够的饼干满足一个孩子，就不要用更大的饼干，因为大饼干可能能满足胃口更大的孩子。这种"资源匹配"类问题，排序加双指针几乎是标配。
3.4 Huffman 合并类：每次合并最小的两个
Huffman 编码的构造过程是贪心的经典应用：每次从待合并的节点中选出权值最小的两个合并，直到只剩一个节点。这个策略保证最终的带权路径长度最小。
实现上通常用优先队列（最小堆）：
import heapq def huffman_cost(weights): heapq.heapify(weights) total = 0 while len(weights) > 1: a = heapq.heappop(weights) b = heapq.heappop(weights) merged = a + b total += merged heapq.heappush(weights, merged) return total为什么每次合并最小的两个是对的？直觉上，权值小的节点应该放在树的更深处（被编码得更长），而它们被合并得越早，参与后续合并的次数就越多，对总代价的贡献反而被"稀释"了。这个证明用交换论证也能做，但理解直觉更重要。我在实现时踩过一个坑：heapify之后直接对原列表操作，如果后续还要用原数据，记得先拷贝一份，否则原列表会被破坏。
4. 贪心失效的三种典型场景：什么时候必须换 DP
4.1 场景一：面额不规则的找零钱
前面提到的找零钱，如果面额是1、3、4，凑6元，贪心给3张，最优是2张。这类问题的本质是：局部最优的选择会破坏后续的最优性。你选了4元，剩下的2元只能用两个1元，而如果一开始选3元，就能用两个3元。贪心在这里没有"后悔"机制，所以失败。
这类问题必须用DP。状态定义为"凑出金额i所需的最少张数"，转移方程是遍历所有面额取最小值。我在Day_28这天特意把找零钱的贪心版和DP版都写了一遍对比，发现DP版虽然代码长，但通用性极强，换任何面额组合都对；贪心版只在特定面额体系下成立。
4.2 场景二：0-1背包问题
0-1背包是贪心失效的另一个经典案例。如果按"单位价值"（价值除以重量）排序，然后贪心地装，会得到次优解。原因是物品不可分割，你无法只装一部分。比如背包容量10，物品A重10价值100，物品B重6价值60、物品C重4价值50。按单位价值排序，A的单位价值是10，B是10，C是12.5，贪心会先装C（价值50），再装B（价值60），总价值110；而最优是装A，价值100……等等，这里110大于100，贪心反而对了。换一组数据：容量10，A重10价值100，B重6价值70，C重4价值40。单位价值A=10，B=11.67，C=10。贪心先装B（70），剩4装C（40），总110；最优是装A，价值100。贪心又对了。
要构造贪心失败的反例，需要更精细的数据。经典反例是：容量10，物品1重6价值60（单位10），物品2重5价值50（单位10），物品3重5价值50（单位10）。贪心按单位价值排序后可能先装物品1，剩4装不下任何东西，总价值60；而最优是装物品2和物品3，总价值100。这个反例说明，当物品不可分割且单位价值相近时，贪心会因为"装了一个大件导致空间浪费"而失败。
4.3 场景三：需要"全局视野"的最优化
有些问题的最优解依赖于对全局信息的综合判断，贪心的"短视"天然不适合。比如"最长递增子序列"（LIS），如果贪心地每次选当前能接上的最小元素，虽然能得到正确长度（配合二分），但这个过程其实已经不是纯粹的贪心了，而是贪心加二分的组合技巧。而如果要求输出具体的子序列，贪心就力不从心了，需要DP或记录前驱。
我总结了一个简单的判断口诀：如果每一步的选择会"锁死"后续的可能性，且锁死之后无法通过其他方式弥补，那就要警惕贪心失效。反过来，如果每一步的选择只是"缩小范围"但不"堵死路"，贪心往往可行。
5. 我的贪心调试方法论：反例优先，证明兜底
5.1 先写反例生成器，再写正解
这是我在Day_28之后养成的一个习惯：在确定贪心策略之前，先花五分钟尝试构造反例。具体做法是，随机生成小规模数据（比如数组长度5到8），用暴力枚举求出真正的最优解，再和贪心解对比。如果找到不一致的用例，说明贪心策略有问题。
import itertools, random def brute_force(items, capacity): best = 0 for r in range(len(items) + 1): for combo in itertools.combinations(items, r): w = sum(x[0] for x in combo) v = sum(x[1] for x in combo) if w <= capacity: best = max(best, v) return best这个暴力函数虽然慢，但只在小数据上跑，用来验证贪心足够了。我用这个方法抓到过好几次自己贪心策略的漏洞，比盯着代码空想高效得多。
5.2 排序字段是贪心最容易出错的地方
回顾我踩过的坑，贪心出错的原因里，排序字段选错占了至少一半。区间调度按开始时间排、分发问题按错误的方向排、合并问题忘了用堆……这些错误的共同点是：策略的"方向"错了，但代码看起来完全正常，不跑用例根本发现不了。
我的应对方法是：每次确定排序字段后，问自己一句"这个字段为什么能代表优先级？"如果答不上来，说明策略还没想清楚，不要急着写代码。比如区间调度按结束时间排，理由是"结束越早，剩余空间越大"，这个理由能说通，才继续写。
5.3 用"交换论证"给策略上保险
对于竞赛或面试场景，光有反例验证还不够，因为反例只能证明"没找到错"，不能证明"一定对"。这时候交换论证就是兜底手段。它的模板是：
- 假设最优解O和贪心解G在第一个不同决策点选择不同。
- 构造一个新解O'，把O中该决策点的选择替换成G的选择。
- 证明O'仍然可行，且目标值不劣于O。
- 由此归纳，贪心解不劣于最优解。
这个证明写出来可能只有几行，但它能让你在面试时理直气壮地说"这个贪心是对的"，而不是"我试了几个用例都过了"。我在准备算法面试时，专门练过把交换论证讲清楚的能力，这比背题有用得多。
6. 贪心与DP的取舍：一张决策表帮你快速定位
学到这里，很多人会问：拿到一道最优化问题，到底该先想贪心还是先想DP？我整理了一张自己常用的决策表，按问题的特征快速定位。
| 问题特征 | 优先考虑 | 原因 |
|---|---|---|
| 每步选择不影响后续可选集合 | 贪心 | 无后效性，局部最优可累加 |
| 选择会改变后续状态空间 | DP | 需要记录状态，避免短视 |
| 需要输出具体方案而非仅最优值 | DP | 贪心通常只维护边界值 |
| 子问题大量重叠 | DP | 记忆化能避免重复计算 |
| 子问题相互独立、无重叠 | 贪心 | 无需存储中间结果 |
| 数据规模大（如10^5以上） | 贪心优先 | DP的O(n^2)可能超时 |
这张表不是绝对的，但能帮我快速缩小思考范围。比如看到"区间调度"，每选一个区间只是缩小了可选范围，不会改变区间本身的性质，所以优先想贪心；看到"背包"，选了物品会改变剩余容量，状态空间被改变，所以优先想DP。
还有一个实操经验：如果一道题贪心和DP都能做，优先用贪心，因为代码短、不易出错、复杂度低。但前提是你已经证明了贪心成立。我见过太多人为了省事直接上贪心，结果被边界用例卡住，最后返工重写DP，反而更费时间。
7. 从Day_28往后：贪心思维的迁移价值
贪心算法学到最后，我发现它最大的价值不在于解题本身，而在于它训练了一种**"在信息不完全时做决策"的思维模式**。现实中很多决策都是贪心的：资源有限时优先满足最紧急的需求、时间紧张时先做收益最高的事。贪心教会我的是：先判断这个问题有没有"局部最优可累加"的结构，如果有，就大胆往前走；如果没有，就要留好回退和记录的余地。
在算法层面，贪心还经常和其他技巧组合出现。比如贪心加二分（用于在单调空间中找最优决策点）、贪心加优先队列（用于动态维护当前最优候选）、贪心加并查集（用于处理带约束的分配问题）。这些组合技我在后续的练习中会陆续展开，Day_28先把纯粹的贪心判断逻辑打牢。
如果你也在学算法，我的建议是：不要跳过贪心的证明环节。很多人觉得"代码过了就行"，但贪心的代码太短，短到掩盖了背后的思考。把交换论证、反例验证这些方法练熟，你收获的不只是一类题的解法，而是一种能迁移到任何最优化问题上的分析框架。这个框架，比记住十道题的模板值钱得多。
