★ FEATURED ARTICLE 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贪心选的第一个区间是BB的结束时间最早。因为B结束最早所以B的结束时间不晚于A。那么把最优解里的A换成B剩下的区间仍然能和B兼容因为B结束更早留给后面的空间更大。所以贪心解不会比最优解差。这个论证链条清晰是理解区间调度的关键。代码实现上排序后维护一个上一个选中区间的结束时间变量即可def max_non_overlapping(intervals): if not intervals: return 0 intervals.sort(keylambda 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. 贪心失效的三种典型场景什么时候必须换 DP4.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的单位价值是10B是10C是12.5贪心会先装C价值50再装B价值60总价值110而最优是装A价值100……等等这里110大于100贪心反而对了。换一组数据容量10A重10价值100B重6价值70C重4价值40。单位价值A10B11.67C10。贪心先装B70剩4装C40总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先把纯粹的贪心判断逻辑打牢。如果你也在学算法我的建议是不要跳过贪心的证明环节。很多人觉得代码过了就行但贪心的代码太短短到掩盖了背后的思考。把交换论证、反例验证这些方法练熟你收获的不只是一类题的解法而是一种能迁移到任何最优化问题上的分析框架。这个框架比记住十道题的模板值钱得多。
阅读完成 · 觉得有帮助？
