贪心算法解题套路框架
raw/articles/2026/05/贪心算法解题套路框架
一句话总结
贪心算法通过局部最优选择推导全局最优解，无需穷举所有可行解，是对回溯和动态规划的进一步剪枝优化。
核心要点
1. 贪心算法与回溯、动态规划的本质区别
算法的本质都是穷举，区别在于穷举的范围和优化手段不同：
| 算法思想 | 优化手段 | 穷举范围 | 算法复杂度 |
|---|---|---|---|
| 回溯算法 | 剪枝优化：提前排除不可能的答案，使树结构尽可能小 | 穷举所有可行解 | 一般指数级别（如 $O(2^n)$） |
| 动态规划 | 备忘录优化：避免重复计算，把树形结构优化成线性结构 | 穷举所有可行解（去重后） | 一般多项式级别（如 $O(n^2)$） |
| 贪心算法 | 推导最优：不需要完整穷举，直接推导最优解 | 不穷举所有可行解 | 可优化到常数级别（如 $O(1)$） |
核心洞察：回溯和动态规划都穷举了所有可行解，试图从中寻找最优解；贪心算法则跳过完整穷举，通过局部最优选择直接推导全局最优。
2. 从回溯到贪心的优化演进（以钞票选择为例）
问题：有1元和100元两种钞票（数量无限），只能选10张，如何使总金额最大？
演进过程：
// 阶段一：回溯思维（穷举所有选择）
int findMax(int n) {
if (n == 0) return 0;
int result1 = 1 + findMax(n - 1); // 选1元
int result2 = 100 + findMax(n - 1); // 选100元
return Math.max(result1, result2);
}
// 复杂度：O(2^n)，二叉树节点数量
// 阶段二：发现重复子问题（动态规划雏形）
// 发现 findMax(n-1) 的值都相同，无需比较两种选择
int findMax(int n) {
if (n == 0) return 0;
return 100 + findMax(n - 1); // 直接选100元
}
// 阶段三：贪心思维（直接推导）
int findMax(int n) {
return 100 * n; // 无需递归，直接计算结果
}
// 复杂度：O(1)
3. 贪心算法的核心思想
- 局部最优 → 全局最优：在某些问题中，每一步都做出当前看起来最优的选择，最终能得到全局最优解
- 无需回溯验证：与回溯/动态规划不同，贪心算法不需要保存和比较所有可行解
- 适用条件：问题必须满足「贪心选择性质」和「最优子结构」
基本原理
贪心选择性质：一个问题可以通过一系列局部最优选择来构造全局最优解。
与动态规划的关系：
- 动态规划：自底向上或自顶向下，通过子问题的最优解构造原问题的最优解
- 贪心算法：可以看作动态规划的特例，当某个子问题的最优解可以通过局部最优选择直接确定时，就可以用贪心
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 贪心选择 | 通常 $O(n)$ 或 $O(1)$ | 取决于具体问题，只需一次扫描或常数计算 |
| 回溯穷举 | 指数级 $O(2^n)$ 或更高 | 需要遍历所有可行解 |
| 动态规划 | 多项式级 $O(n^2)$ 等 | 需要计算所有子问题 |
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 55. 跳跃游戏 | 中等 |
| LeetCode | 45. 跳跃游戏 II | 中等 |
相关概念
相关实体
- labuladong：本文来源，算法教学网站
总结
贪心算法是对回溯和动态规划的进一步剪枝——不只是减少穷举范围（回溯）或避免重复计算（动态规划），而是直接跳过完整穷举，通过局部最优选择推导全局最优解。其前提是问题具有「贪心选择性质」，即局部最优能导致全局最优。
注意事项
- 贪心算法并非适用于所有优化问题，必须验证贪心选择性质是否成立
- 与动态规划相比，贪心算法难以证明正确性，需要严格的数学证明
- 实践中，可以先尝试贪心，再用动态规划验证（如果问题规模允许）