贪心算法的思想

贪心算法的基本思想是如果当前最优，则全局最优。

  • 具有贪心选择性质的问题一般都需要证明。
  • 如果不具有贪心选择性质，则只需要举一个反例即可。

贪心算法，又称贪婪算法。
1、在对问题求解时，总是做出在当前看来最好的选择。即贪心算法不从整体最优上加以考虑。
2、贪心算法所作出的是在某种意义上的局部最优解。
贪心算法和动态规划算法都是由局部最优导出全局最优，二者的区别如下。
贪心算法： 1、贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。 2、贪心法正确的前提是：每一步的最优解一定包含上一步的最优解。
动态规划： 1、全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解；2、动态规划的关键是确定“状态转移方程”，即如何通过已经求出的局部最优解推导出全局最优解； 3、边界条件：即最简单的，可以直接得出的局部最优解。

贪心算法的引用：
1、单源最短路径（待讨论）；
2、最小生成树；
3、哈夫曼编码。

image.png

435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

思路：
贪心。先排序。
动态规划。类似300. 最长上升子序列。

  1. class Solution {
  2.     public int eraseOverlapIntervals(int[][] intervals) {
  3.         if (intervals == null || intervals.length <= 1) return 0;
  5.         Arrays.sort(intervals, (x, y) -> x[1] - y[1]);
  7.         int bound = intervals[0][1], res = 0;
  8.         for (int i = 1; i < intervals.length; ++i) {
  9.             if (intervals[i][0] < bound) res++;
  10.             else bound = intervals[i][1];
  11.         }
  13.         return res;
  14.     }
  15. }

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

思路：本题用一个数 max_arrive 表示能到达的最远下标，一步步走下去，如果发现在 max_arrive 范围之内某处能达到的范围大于 max_arrive，那么我们就用更大的范围来替换掉原先的 max_arrive，这样一个局部的最优贪心策略，在全局看来也是最优的，因为局部能够到达的最大范围也是全局能够到达的最大范围。
方法一：暴力解法（最后一个测试用例超时）

class Solution {
    private boolean res = false;
    public boolean canJump(int[] nums) {
        helper(nums, 0);
        return res;
    }

    private void helper(int[] nums, int k) {
        if (res == true) {
            return;
        }
        int cur = nums[k];
        if (cur + k >= nums.length - 1) {
            res = true;
        } else {
            for (int i = k + 1; i <= k + cur; i++) {
                helper(nums, i);
            }
        }
    }
}

练习：

402. 移掉K位数字

12. 整数转罗马数字

13. 罗马数字转整数

45. 跳跃游戏 II

455. 分发饼干

452. 用最少数量的箭引爆气球