什么是贪心算法？它和动态规划有什么区别？

简化版

贪心算法是每一步都做当前看起来最好的选择（局部最优），并期望这一串局部最优能拼出全局最优。它不回头、不撤销，一步定终身。和动态规划最大的区别是：DP 会枚举/保留多种状态再择优，贪心只沿一条路走到底。贪心的核心难点不是写代码（往往就是排序 + 一次遍历），而是证明「局部最优真的能推出全局最优」——能证明才敢用。

详细版

贪心成立的两个条件：

贪心选择性质：全局最优解可以通过一系列局部最优选择得到——即当前这一步选眼下最优的，不会堵死未来通向最优解的路。
最优子结构：做完当前选择后，剩下的子问题的最优解 + 当前选择，仍是原问题的最优解。

贪心 vs 动态规划：

维度	贪心	动态规划
决策	每步只选当前最优，不回退	枚举所有子状态，保留后再择优
是否记录状态	一般不需要额外状态表	需要 `dp` 数组记录子问题解
正确性	需要证明贪心选择性质	只要状态转移正确必对
时间	通常 O(n) 或 O(n log n)（含排序）	通常 O(n²) 或更高
典型题	分发饼干、跳跃游戏、区间调度	背包、最长公共子序列、编辑距离

常见解题套路：

排序后贪心：先按某个维度排序，再线性扫描（区间调度、分发饼干、重建队列）。
维护一个当前最优量：如「当前能到的最远位置」「当前最小成本」，边扫边更新（跳跃游戏、买卖股票）。

完整版教学

一、贪心到底「贪」什么

贪心算法的思想极其朴素：面对一个要做很多步决策的问题，每一步都不做通盘规划，只挑当前这一步收益最大（或代价最小）的选项，选完就定死、绝不反悔。 走完所有步骤，如果运气好——准确说，如果问题结构允许——这一串短视的选择恰好拼出了全局最优解。

举个生活例子：找零钱要用最少的纸币，面额有 100、50、20、10、5、1。找 168 元，你会本能地先拿最大的：1 张 100，再 1 张 50，再 1 张 10，再 1 张 5，再 3 张 1……这就是贪心——每次都拿「不超过剩余金额的最大面额」。对这套面额它恰好总能得到最少张数。

但注意「运气好」三个字：贪心不是万能的。如果面额换成 [1, 3, 4]，凑 6 元，贪心先拿 4，剩 2 只能拿两个 1，共 3 张；而最优是 3+3 两张。这里贪心就错了——因为拿 4 这个「局部最优」把路堵死了。这正是为什么贪心的灵魂在于证明，而不是编码。

二、贪心成立的两块基石

一个问题能用贪心，必须同时满足两点：

① 贪心选择性质（Greedy Choice Property）

「整体最优解可以由局部最优选择推导出来」。换句话说：存在一个全局最优解，它的第一步恰好就是我们贪心选的那一步。证明常用交换论证法（exchange argument）：假设有个最优解第一步没选贪心项，那我把它换成贪心项，证明结果不会更差——于是「选贪心项」也能达到最优。

② 最优子结构

做完当前贪心选择后，问题缩小为一个同类型的子问题，且「原问题最优解 = 当前选择 + 子问题最优解」。这一点贪心和 DP 是共享的，区别在下一节。

记住：贪心选择性质是贪心区别于 DP 的关键。DP 不要求它——DP 老老实实枚举所有选择再挑最好的，所以哪怕没有贪心选择性质也对，只是慢。

三、和动态规划到底差在哪

很多人分不清贪心和 DP，因为两者都讲「最优子结构」。核心分水岭是面对当前这一步，你敢不敢只选一个方向：

DP：不敢。它把「当前步的所有可能选择」都试一遍，各自解完子问题，最后 min/max 挑最好的——所以要用 dp[] 数组把各种状态的解都存下来备查。
贪心：敢。它笃定「当前局部最优就是通向全局最优的那一步」，于是只走这一条路，不需要保留其他状态，一遍扫过去就完事。

拿零钱兑换对比最清楚：

面额 [1,2,5] 凑 11，贪心（每次拿最大）对，因为这套面额满足贪心选择性质。
面额 [1,3,4] 凑 6，贪心错，必须用 DP（dp[j]=min(dp[j], dp[j-coin]+1)）枚举每种硬币才能得到最优的 3+3。

所以面试里有个经验法则：当你「拍脑袋想到的贪心策略」无法严格说服自己时，老老实实上 DP；能证明贪心正确时，贪心更快更简洁。

四、两大实战套路

绝大多数贪心题落在两个模板里：

套路一：排序 + 线性扫描

先按关键维度排序，让「贪心的顺序」显现出来，再一遍扫描做选择。典型：

区间调度（无重叠区间、用箭射气球）：按右端点排序，每次选结束最早的，给后面留最多空间。
分发饼干：胃口和饼干都排序，小饼干喂小胃口，物尽其用。
重建队列：按身高降序、k 升序排序后依次插入。

套路二：一次遍历维护「当前最优量」

不排序，边遍历边维护一个滚动的最优指标：

跳跃游戏：维护「当前能到达的最远下标 farthest」，扫一遍看能否覆盖终点。
买卖股票 II：只要今天比昨天贵就把差价收进口袋，累加所有上坡。
最大子数组和（Kadane）：维护「以当前元素结尾的最大和」，负了就丢弃重启。

五、怎么快速判断一道题能不能贪心

面试现场没时间写严格证明，给你几条实用直觉：

先想一个贪心策略，再手动找反例。找不到反例（尤其是小规模穷举验证过）就大胆用；能找到反例就换 DP。
「求最值 + 每一步的选择互不冲突/有明显偏序」 往往能贪心（区间、排序类）。
「选择之间会互相影响、此消彼长、需要权衡」 往往要 DP（背包：拿了这件就少了容量装别的）。
经典贪心题就那几类：区间调度、跳跃覆盖、股票上坡、Huffman 编码、找零（特定面额）、重建队列——见到眼熟的直接套。

易错点：别把「暂时能跑对样例」当成贪心正确。贪心最坑的就是小样例过了、大样例或刁钻数据翻车。心里没底就上 DP，稳。

六、贪心选择为什么不会堵死未来

本题每一步选择是：每一步只保留一个“对未来最宽松”的局部选择，必须证明存在某个全局最优解以该选择开头。

正确性不能只靠直觉，核心证明是：交换论证把任意最优解的首选替换为贪心选择且不变差；或证明领先性质始终不落后。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：活动选择按最早结束选 [1,2]，给后续留下最长时间；选更晚结束的区间可被它替换。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：不能用几个样例代替证明；局部最优若影响未来状态且无法安全替换，通常需要 DP。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

八、常见误区与追问

误区：看起来合理的局部最优就是贪心。 必须证明贪心选择性质与最优子结构。
误区：贪心一定比 DP 快。 常见如此，但是否正确取决于问题结构。
误区：排序只是实现细节。 排序往往构造了可证明的选择顺序。
追问：交换论证怎么做？ 把任意最优解的不同首选换成贪心选择并证明不变差。
追问：失败时怎样识别？ 构造局部最好却导致后续更差的反例。
追问：贪心与 DP 的核心差别？ 贪心永久提交选择，DP 保留多个状态再比较。

九、加强记忆

贪心 = 每步只选当前局部最优、选完不反悔，赌一串局部最优能拼成全局最优。用它的前提是能证明贪心选择性质（全局最优可由局部最优推出，常用交换论证）+ 最优子结构。和 DP 的根本区别：DP 枚举所有状态再择优（要状态表、慢但稳），贪心只走一条路（无需状态、快但需证明）；证不出贪心正确就上 DP。实战两套路——排序+扫描（区间/饼干/重建队列）和一遍遍历维护当前最优量（跳跃/股票/Kadane）。判断能否贪心的土办法：想个策略、手动找反例，找不到就用。

简化版

详细版