3.5 贪心算法
3.5 贪心算法
什么是贪心算法？
贪心算法，又称贪婪算法，在对问题求解时，总是做出在当前看来最好的选择，期望通过每个阶段的局部最优选择达到全局最优，但结果不一定最优。
适用场景
简单的说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就能用贪心算法的到最后的最优解，这种子问题最优解称为最优子结构。
贪心算法与动态规划的区别
贪心算法与动态规划的不同点在于它对每个子问题的解决方案都做出当前的最优选择，不能回退，而动态规划会保留之前的运算结果，并根据之前的结果进行选择，有回退的功能，贪心是动态规划的理想化的情况。
相关题目
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
|---|---|---|---|---|---|
| 455 | 分发饼干 | 贪心 数组 双指针 1+ | 🟢 | 🀄️ 🔗 | |
| 860 | 柠檬水找零 | 贪心 数组 | 🟢 | 🀄️ 🔗 | |
| 56 | 合并区间 | [✓] | 数组 排序 | 🟠 | 🀄️ 🔗 |
| 435 | 无重叠区间 | [✓] | 贪心 数组 动态规划 1+ | 🟠 | 🀄️ 🔗 |
| 452 | 用最少数量的箭引爆气球 | [✓] | 贪心 数组 排序 | 🟠 | 🀄️ 🔗 |
| 55 | 跳跃游戏 | [✓] | 贪心 数组 动态规划 | 🟠 | 🀄️ 🔗 |
| 45 | 跳跃游戏 II | [✓] | 贪心 数组 动态规划 | 🟠 | 🀄️ 🔗 |
| 392 | 判断子序列 | [✓] | 双指针 字符串 动态规划 | 🟢 | 🀄️ 🔗 |
| 122 | 买卖股票的最佳时机 II | [✓] | 贪心 数组 动态规划 | 🟠 | 🀄️ 🔗 |
| 561 | 数组拆分 | 贪心 数组 计数排序 1+ | 🟢 | 🀄️ 🔗 | |
| 1710 | 卡车上的最大单元数 | 贪心 数组 排序 | 🟢 | 🀄️ 🔗 | |
| 1217 | 玩筹码 | 贪心 数组 数学 | 🟢 | 🀄️ 🔗 | |
| 1247 | 交换字符使得字符串相同 | 贪心 数学 字符串 | 🟠 | 🀄️ 🔗 | |
| 1400 | 构造 K 个回文字符串 | 贪心 哈希表 字符串 1+ | 🟠 | 🀄️ 🔗 | |
| 921 | 使括号有效的最少添加 | [✓] | 栈 贪心 字符串 | 🟠 | 🀄️ 🔗 |
| 1029 | 两地调度 | 贪心 数组 排序 | 🟠 | 🀄️ 🔗 | |
| 1605 | 给定行和列的和求可行矩阵 | 贪心 数组 矩阵 | 🟠 | 🀄️ 🔗 | |
| 135 | 分发糖果 | [✓] | 贪心 数组 | 🔴 | 🀄️ 🔗 |
| 134 | 加油站 | [✓] | 贪心 数组 | 🟠 | 🀄️ 🔗 |
| 53 | 最大子数组和 | [✓] | 数组 分治 动态规划 | 🟠 | 🀄️ 🔗 |
| 376 | 摆动序列 | 贪心 数组 动态规划 | 🟠 | 🀄️ 🔗 | |
| 738 | 单调递增的数字 | 贪心 数学 | 🟠 | 🀄️ 🔗 | |
| 402 | 移掉 K 位数字 | 栈 贪心 字符串 1+ | 🟠 | 🀄️ 🔗 | |
| 861 | 翻转矩阵后的得分 | 贪心 位运算 数组 1+ | 🟠 | 🀄️ 🔗 | |
| 670 | 最大交换 | [✓] | 贪心 数学 | 🟠 | 🀄️ 🔗 |