贪心算法：贪心策略、正确性证明、经典例题

贪心算法，说白了就是「每一步都选当前最优，最后希望全局最优」。

听起来很简单对吧？但我在项目中踩过不少坑。有一次做资源调度，我拍脑袋用了贪心，结果跑出来的方案比随机分配还差。后来我才明白——贪心不是万能药，它需要严格的正确性证明。

贪心策略的核心思想

贪心算法的本质是局部最优推导全局最优。它不做回溯，不搞动态规划那套「记住所有状态」的玩法。每一步只盯着眼前利益，像个短视的决策者。

我个人习惯把贪心策略分成三步：

1. 拆解子问题：把大问题切成一个个小步骤
2. 定义贪心选择：明确每一步「最优」的标准是什么
3. 证明最优子结构：局部最优能拼出全局最优

正确性证明——避坑指南

我曾经在面试时被问到：「你凭什么觉得贪心是对的？」当时我支支吾吾答不上来。后来我总结了两种最常用的证明方法：

1. 交换论证法

假设最优解和贪心解不一样，然后通过交换元素，证明贪心解可以变成最优解而不损失质量。说白了就是「你最优解里有的，我贪心解也能有」。

2. 数学归纳法

证明第1步贪心选择是对的，然后假设前k步都对，证明第k+1步也对。这招在区间调度里特别好使。

经典例题一：区间调度

问题描述：给你一堆区间[start, end]，选出尽可能多的互不重叠的区间。

你想想看，怎么选？我刚开始做这道题时，试过按开始时间排序，也试过按区间长度排序，结果都不对。正确答案是按结束时间最早排序。

为什么？因为结束得越早，留给后面的空间就越大。这就是贪心选择——每次选结束最早的区间。

// 区间调度 - 贪心解法
function intervalSchedule(intervals) {
  // 按结束时间升序排序
  intervals.sort((a, b) => a[1] - b[1]);
  
  let count = 0;
  let lastEnd = -Infinity;
  
  for (let [start, end] of intervals) {
    if (start >= lastEnd) {
      count++;
      lastEnd = end;  // 更新最后结束时间
    }
  }
  
  return count;
}

经典例题二：零钱兑换

问题描述：给定不同面额的硬币，用最少的硬币凑出目标金额。

嗯，这里要注意——贪心解法只适用于硬币面额是「规范」的情况。比如人民币的1、2、5、10，或者美元的1、5、10、25。这些面额之间满足倍数关系，贪心才有效。

但如果硬币面额是1、3、4，目标金额是6，贪心会选4+1+1（3枚），而最优解是3+3（2枚）。你看，翻车了吧？

// 零钱兑换 - 贪心解法（仅适用于规范面额）
function coinChangeGreedy(coins, amount) {
  // 按面额降序排序
  coins.sort((a, b) => b - a);
  
  let count = 0;
  let remaining = amount;
  
  for (let coin of coins) {
    if (remaining === 0) break;
    let num = Math.floor(remaining / coin);
    count += num;
    remaining -= num * coin;
  }
  
  return remaining === 0 ? count : -1;
}

贪心算法的知识体系

下面这张图是我自己整理的贪心算法知识结构，你看一眼就能明白整体脉络：

贪心 vs 动态规划

很多初学者分不清贪心和DP。我打个比方你就懂了：

• 贪心：像爬山时只看脚下，选最陡的路往上爬。快，但可能爬到小山坡就停了。
• DP：像拿着地图爬山，把所有路径都算一遍再选。慢，但保证找到最高峰。

对比维度	贪心算法	动态规划
决策方式	只做一次选择，不回头	记录所有子问题解，择优
时间复杂度	通常 O(n) 或 O(n log n)	通常 O(n²) 或更高
正确性证明	需要严格证明	依赖状态转移方程
适用场景	区间调度、最小生成树	背包问题、编辑距离

实战小技巧

最后分享几个我在项目中积累的贪心使用心得：

• 排序是贪心的灵魂：90%的贪心问题都需要先排序。排序标准选对了，问题就解决了一半。
• 边界条件别漏：空数组、单元素、所有区间都重叠——这些情况我全踩过坑。
• 先写暴力再优化：如果拿不准贪心对不对，先写个暴力解做对照。测试通过后再换成贪心，心里踏实。

---