贪心算法
大约 1 分钟
贪心算法
贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
贪心算法没有套路，说白了就是常识性推导加上举反例。
习题
455: 分发饼干
1005: K次取反后最大化的数组和
860: 柠檬水找零
376: 摆动序列
738: 单调递增的数字
122: 买卖股票的最佳时机II
714: 买卖股票的最佳时机含手续费
135: 分发糖果
406: 根据身高重建队列
55: 跳跃游戏
45: 跳跃游戏II
452: 用最少数量的箭引爆气球
435: 无重叠区间
763: 划分字母区间
56: 合并区间
53: 最大子序和
134: 加油站
968: 监控二叉树