贪心啊贪心

贪心就是每次都选择一个局部最优解，推到最后得到一个全局最优解。

动态规划不一样的是，动态规划的每一步的不同选择会导致最后结果的不同。

比如从一堆纸币里选择10次怎么选出来额度最高，适用贪心算法就是每次都从那堆纸币里拿出面额最大的一张，这样选择10次以后得到的总面额肯定是最大的。

又比如在一个二维数组的矩形路径上，要选择一条花费最少的路径，这一步的选择会影响下一步的选择，这种情况就应该用动态规划。

那么贪心是不是就是动态规划的特殊情况。

leetcode 455 分饼干

小孩胃口数组g = [1,2,3]，饼干大小数组s = [1,1]

解题思路就是用大饼干给大胃口的孩子，因为用大饼干给小胃口的孩子就会浪费。

    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;
        // 遍历胃口
        for (int index = g.length - 1; index >= 0; index--) {
            if(start >= 0 && g[index] <= s[start]) {
                start--;
                count++;
            }
        }
        return count;
    }

leetcode 376 摆动序列

如果要去模拟删除元素达到最长摆动子序列的过程，就会非常复杂，一时半会儿想不清楚。保持区间波动，只需要把单调区间上的元素移除就可以了。 

贪心解法： 

    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        //当前差值
        int curDiff = 0;
        //上一个差值
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            //得到当前差值
            curDiff = nums[i] - nums[i - 1];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }

 动态规划解法：

    public int wiggleMaxLength(int[] nums) {
        // 0 i 作为波峰的最大长度
        // 1 i 作为波谷的最大长度
        int dp[][] = new int[nums.length][2];

        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.length; i++){
            //i 自己可以成为波峰或者波谷
            dp[i][0] = dp[i][1] = 1;

            for (int j = 0; j < i; j++){
                if (nums[j] > nums[i]){
                    // i 是波谷
                    dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
                }
                if (nums[j] < nums[i]){
                    // i 是波峰
                    dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
                }
            }
        }

        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }