06-贪心算法

type
status
date
slug
summary
tags
category
icon
password
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前最优解（局部最优），从而希望得到整体最优解（全局最优解）的方法。
在当前阶段做出局部最优选择，且不回退。
  • 每一步都选对当前最有利的选择
  • 不考虑未来影响
  • 不回溯、不动态规划
贪心算法并不总是正确，适用于满足最优子结构和贪心选择性质的问题：
  1. 最优子结构：问题的整体最优解可以由子问题的最优解构造而成；
  1. 贪心选择性质：通过局部最优选择，能导致全局最优结果。
一般使用贪心前要能严格证明或反证法验证其正确性。
  1. 排序是常用手段（如按值/权重/截止时间等）
  1. 每一步都选最优的选择
  1. 判断是否满足贪心性质（必要时构造反例）
  1. 注意是否需要证明贪心策略正确性（特别是 AC 自动判断题）
问题
说明
是否适用贪心
零钱兑换（最少硬币数）
✅ 如果是美制面额 (1,5,10,25...)
有些币值不适用
活动选择 / 区间调度
选择最多不重叠活动
✅
Huffman 编码
最短前缀编码
✅
跳跃游戏 Jump Game
是否能跳到终点
✅
加油站问题
每次加最少的油
✅
分发饼干
每个孩子分到最小满足的饼干
✅

分发饼干（LeetCode 455）

跳跃游戏（LeetCode 55）

合并区间（LeetCode 56）

加油站问题（LeetCode 134）

 

与动态规划的比较

特性
贪心
动态规划
选择策略
当前最优
所有可能都考虑
适用范围
问题结构简单
状态复杂、需记忆
回溯
否
否
解的准确性
需证明，可能错误
正确（假设状态设计无误）
 
上一篇
05-动态规划
下一篇
07-分治算法
Loading...