跳到主要内容

贪心算法

贪心算法（Greedy Algorithm）是指在对问题求解时，总是做出在当前看来是最好的选择。

贪心的局限性​

贪心算法并不从整体最优上加以考虑，它所做出的是在某种意义上的 局部最优解。因此，贪心算法并不一定能得到整体最优解，但对很多特定问题，贪心策略确能产生全局最优解。

贪心的适用条件​

  1. 贪心选择性质：问题的全域最优解可以通过一系列局部最优（贪心）选择来实现。
  2. 最优子结构性质：问题的最优解包含其子问题的最优解。

贪心算法解题步骤​

  1. 建立数学模型：描述问题。
  2. 将求解的问题分成若干个子问题。
  3. 对每个子问题求解，得到子问题的局部最优解。
  4. 把子问题的局部最优解合成原来解问题的一个解。

经典实例：单源最短路径​

  • Dijkstra 算法：贪心地选择距离最近的未访问点，这就能得到全局最短路径。

经典实例：分发糖果 (LeetCode 135)​

每个孩子都有一个评分，评分高的多拿。

  1. 贪心策略：从左往右遍历一次（处理左邻居），再从右往左遍历一次（处理右邻居），最后取最大。

经典贪心问题​

1. 区间问题 (Interval Problems)​

  • 活动安排：在一定时间内安排最多的活动。策略：按照 活动结束时间 从小到大排序。
  • 无重叠区间：按照结束时间排序，能获得全局最优。

2. 跳跃游戏 (Jump Game)​

  • 贪心策略：只需维护当前能达到的 最远距离 maxPos。

3. 股票买卖 II (Unlimited Transactions)​

  • 贪心策略：只要明天比今天涨，今天就买、明天就卖。其利润总和即为全局最优。

4. 钱币找零问题​

  • 策略：优先给面额最大的。注意：仅在某些特定面额组合下（如人民币、美元系统）贪心能成，否则需要 DP。

练习​

  1. LeetCode 455：分发饼干 (最简单贪心)
  2. LeetCode 55/45：跳跃游戏 I/II (维护远方边界)
  3. LeetCode 135：分发糖果 (经典两次扫描)
  4. LeetCode 435/452：无重叠区间 (区间调度贪心)
  5. LeetCode 763：划分字母区间
  6. LeetCode 134：加油站 (单次线性扫描核心)
  7. 理解 霍夫曼编码 (Huffman Coding)：基于频度的贪心生成最优的前缀编码系统。