算法里有个思想特别符合人的直觉，叫贪心算法（也有人叫贪婪算法，一回事）。

它的核心就俩字：贪。 每一步都抓眼前看起来最好的那个选择，一路贪下去，指望最后能攒出一个整体最优的结果。

这篇不写代码，就用几个生活里的例子加图，把贪心讲清楚——它怎么想事情、啥时候灵、啥时候会翻车。

贪心到底是个啥思路

先把这个“贪”字讲透。

贪心算法做决定时，只看当前这一步哪个选择最划算，选完就定死，绝不回头。它压根不去考虑“我现在这么选，会不会害得后面吃亏”。

用人话说就是：走一步看一步，每步都挑眼前最甜的，管它以后。

举个最接地气的：你面前有一堆钞票，让你拿 5 张，怎么拿最多钱？

凭直觉你就会用贪心——每次都抓面额最大的那张，抓 5 次。这就是贪心，简单粗暴，而且这个场景它还真对。

它的优点很突出：

• 思路简单，符合直觉，好想好写
• 速度快，每步只做个局部判断，不用回头、不用穷举

但它有个致命毛病，后面细说。先看两个它表现好的例子。

例子一 找零钱

这是讲贪心最经典的例子。

假设你是收银员，要找给顾客 63 元，手上有 50、20、10、5、1 这几种面额，怎么找张数最少？

贪心的做法：每次都先拿能用的最大面额。

要找: 63 元

第1步: 拿 50  ->  还差 13   (50 <= 63,能拿最大的)
第2步: 拿 10  ->  还差 3    (20 太大了,退而拿 10)
第3步: 拿 1   ->  还差 2
第4步: 拿 1   ->  还差 1
第5步: 拿 1   ->  还差 0   搞定

结果: 50 + 10 + 1 + 1 + 1 = 63,一共 5 张
​

每一步都贪最大的，5 张搞定。在这套面额下，贪心给出的就是最优解，又快又对。

收银员找零其实天天在用贪心，只是没意识到罢了。

例子二 排活动

再看一个也很典型的：一个会议室，一天里有好多活动想用，每个活动有开始和结束时间，同一时刻只能有一个活动占用。怎么安排能塞进最多的活动？

贪心的诀窍是：每次都选“结束时间最早”的那个活动。

为啥挑结束早的？因为它结束得早，给后面腾出的空间就最多，能容下更多活动。

活动(按结束时间排好):
  A ===>          (9:00-10:00)
  B   ======>     (9:30-11:30)
  C        ===>   (10:00-11:00)
  D           ==> (11:00-12:00)

贪心挑选:
  先选 A(最早结束 10:00)
  B 跟 A 时间撞了,跳过
  选 C(10:00 开始,不撞),结束 11:00
  选 D(11:00 开始,不撞)

结果: A + C + D,塞进 3 个活动
​

每次贪“最早结束”的，一路选下来就能排进最多活动。这个例子里，贪心也给出了最优解。

关键的坑 贪心会翻车

看到这你可能觉得贪心挺神。别急，它有个大坑：贪心不保证得到全局最优解。

因为它只顾眼前，从不回头。眼前最优，攒起来未必是整体最优。

还拿找零钱举例，但换一套“奇葩”面额：假设只有 1、5、11 三种面额，要找 15 元。

贪心会怎么做？

贪心(每次拿最大):
  拿 11  ->  还差 4
  拿 1   ->  还差 3
  拿 1   ->  还差 2
  拿 1   ->  还差 1
  拿 1   ->  还差 0
  结果: 11 + 1 + 1 + 1 + 1 = 15,共 5 张

可实际上最优是:
  5 + 5 + 5 = 15,只要 3 张!
​

看到了吧？贪心一上来贪了个 11，把自己带沟里了，最后用了 5 张。而不贪那个 11、老老实实用三个 5，只要 3 张。

贪心被眼前的“最大”骗了，错过了全局更优的解。 这就是它翻车的样子。

为啥前面 63 元那套面额（50/20/10/5/1）贪心就对、这套（1/5/11）就错？因为贪心灵不灵，取决于问题本身的性质，不是所有问题都适合它。

那什么时候能用贪心

既然会翻车，用之前就得掂量。判断一个问题能不能用贪心，看两个性质：

• 贪心选择性质：每一步选当前最优，确实能通向全局最优（比如活动选择里“选最早结束的”这个策略被证明是对的）
• 最优子结构：大问题的最优解，包含着子问题的最优解（问题能一层层拆，拆开各自最优拼起来还是最优）

这两条听着抽象，落到实践就一句大白话：

别默认贪心一定对。想用它，先证明它对；证不了，就老实用别的方法（比如动态规划）去枚举更多可能。

那套 1/5/11 的面额，贪心不满足“贪心选择性质”，所以它就是错的。而标准货币面额（1/5/10/50 这种）是特意设计过的，贪心恰好成立，这才是我们平时找零能放心贪的原因。

小结

贪心算法这东西，简单归简单，用起来得留个心眼：

• 核心思路：每步都选眼前最优，绝不回头，指望攒出全局最优
• 优点：思路直觉、代码好写、速度快
• 致命坑：只顾眼前，不保证全局最优（1/5/11 找 15 元就翻车了）
• 用之前先验证：满足贪心选择性质和最优子结构才能用，否则老实上动态规划这类方法

一句话记住它的性格：贪心是个只看眼前、从不后悔的乐观主义者。 它有时能一路顺到全局最优，有时也会被眼前的甜头带进坑。用它之前，先问一句“这题真能贪吗”，别上来就贪。那就找几道题，掂量掂量能不能贪吧。