Skip to main content

​
核心认知

贪心算法就是每一步都先做当前看起来最优的选择。 它和动态规划最大的区别在于：
  • 贪心不回头
  • 贪心不枚举所有状态
  • 贪心希望用局部最优推出全局最优
所以贪心题最难的地方通常不是写代码，而是证明当前的选择为什么不会错。

​
贪心题为什么总让人“感觉能做”

因为很多题第一眼都会让你觉得： “这一步先选最大的 / 最小的 / 最早结束的，应该没问题吧。” 真正的关键在于，这个“应该”能不能被证明。 如果你只能靠直觉，就很容易在边界情况里翻车。

​
一个最经典的 Python 例子

区间调度是贪心里很经典的模型。 
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda item: item[1])
    count = 0
    end = float("-inf")

    for start, finish in intervals:
        if start >= end:
            count += 1
            end = finish

    return len(intervals) - count
这里真正的贪心点在于：
  • 总是优先选择结束更早的区间
因为结束得越早，给后面留下的空间越大。

​
贪心常见题型

贪心题经常出现在这些方向：
  • 区间问题
  • 跳跃游戏
  • 股票买卖中的部分模型
  • 分发类问题
  • 资源最少 / 收益最大问题
很多题一旦找到了排序规则，后面的实现就会突然简单。

​
如何判断能不能用贪心

可以先问自己三个问题：
  1. 当前最优选择会不会破坏后面的最优性？
  2. 能不能证明最优解一定包含当前选择？
  3. 有没有明显的排序规则或优先级规则？
如果这些问题有稳定答案，贪心通常就值得尝试。

​
贪心和动态规划的区别

贪心更强调：
  • 当前这一步怎么选
动态规划更强调：
  • 当前状态如何由之前状态转移而来
如果题目无法保证局部最优可以推出全局最优，就要警惕它更可能属于动态规划。

​
学习建议

建议按这个顺序练：
  • 分发饼干
  • 摆动序列
  • 最大子数组和
  • 跳跃游戏
  • 区间问题
当你开始主动寻找“排序规则”和“选择依据”时，贪心题会越来越顺。