摘要

• 贪心算法可以认为是动态规划算法的特例。对于可能具有贪心选择性质的问题，可以先尝试贪心算法，看运行结果是否正确，贪心算法不对则退一步，用动态规划求解。
• 或许应该先复习动态规划再复习贪心算法，贪心算法太巧妙了，如果没有选择正确的贪心策略，还是很难解决问题的。

贪心算法理论基础

1. 和动态规划的关系

• 贪心算法可以认为是动态规划算法的特例，和动态规划相比，使用贪心算法解题需要问题满足额外的条件（即贪心选择性质）

2. 贪心选择性质

2.1 概念

• 贪心选择性质，直观地去理解，就是每一步都做出一个局部最优的选择，逐步的局部最优直到最终的结果是全局最优。
• 这是一个特殊的性质，只有一部分问题满足这个性质。

2.2 要不要证明？

• 贪心选择性质的判断和证明目前还没有简单的通法，一般可以通过数学归纳法和反证法来进行严谨的数学证明，但耗时较长，相对于解题时间来说得不偿失。和严谨地证明贪心选择性质相比，直接尝试贪心算法，看最终结果是否正确，或者能不能举出反例来说明不能用贪心效率更高。
• 对于可能具有贪心选择性质的问题，可以先尝试贪心算法，贪心算法不正确再退一步使用动态规划。

2.3 贪心算法的思考步骤

从贪心选择性质的概念出发，每一步的局部最优最终导致全局最优。在解决一个具体问题是，这需要我们明确以下三步：

1. 每一步（即子问题）是什么，如何把问题分解成子问题，或者说模拟求解的过程中如何定义“一步”怎么走。
2. 这一步的局部最优是什么
3. 全局最优是什么
4. 最后再尽量用一句话来总结贪心选择的过程

贪心算法确实没有固定的模板或者套路，但形成一套自己的方法论还是有必要的，不能漫无目的的思考。

LeetCode455 分发饼干

455. 分发饼干 - 力扣（Leetcode）

• 每一步是什么：把一块饼干j分给一个孩子i，这就是这个问题中的一步。
• 这一步的局部最优是什么：把一块饼干分给一个孩子，只有能满足胃口和不能满足胃口两种结果。饼干j能满足孩子i的胃口当然是必要的，局部最优的情况可能是：饼干j能恰好满足孩子i的胃口，或者只比孩子i的胃口稍大，这样就不会浪费饼干的尺寸。
• 全局最优是什么：题目帮我们定义好了，就是尽可能满足越多数量的孩子。
• 对饼干的尺寸值进行升序排序，对孩子的胃口值也进行升序排序，方便我们先将小的饼干分给胃口小的孩子。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0;
        if (g.empty() || s.empty()) return i;// 没有孩子或者没有饼干，都返回0
        for (int j = 0; j < s.size(); j++) {// 把一块饼干
            if (s[j] >= g[i]) i++;// 尝试分给一个孩子
            if (i >= g.size()) break;// 每位孩子的胃口都满足了，不用再分了
        }
        return i;
    }
};

LeetCode376 摆动序列

376. 摆动序列 - 力扣（Leetcode）

• 先考虑边界条件，题目说“仅有一个元素或者含两个不等元素的序列也视作摆动序列”，那先过滤掉只有一个元素的情况。

if (nums.size() < 2) return nums.size();

• 每一步是什么：选两个相邻的数字nums[i - 1]和nums[i]，判断这两个数字是不是摆动序列。
  • 第一步：这两个数字不相等，那构成一个长度为2的摆动序列，并保存这两个元素的差值last
  • 之后的步骤：i向右移一位，判断新的nums[i - 1]和nums[i]的差值是否与last异号。摆动序列中相邻的两位数字不能相等，如果nums[i - 1] == nums[i]即相邻元素的值相等，最终应该至多只保留一个元素。考虑到相邻元素相等的情况，(nums[i - 1] - nums[i]) * last < 0判断异号的条件应该改为(nums[i - 1] - nums[i]) * last <= 0。
• 局部最优：nums[i - 1] - nums[i]不等于0且与last异号。
• 全局最优，即找到最长的摆动序列的长度。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        int last = 0;// 假设 nums[0] == nums[1]
        int count = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i - 1] == nums[i]) {// 相邻元素相等，直接右移
                continue;
            }
            if ((nums[i - 1] - nums[i]) * last <= 0) {
                // nums[0] != nums[1] 时可以执行到这里
                last = nums[i - 1] - nums[i];
                // 之后不会再出现(nums[i - 1] - nums[i]) * last == 0的情况
                // 除了第一步，上面的判断条件就是nums[i - 1] - nums[i]与last异号
                count++;
            }
        }
        return count;
    }
};

LeetCode53 最大子数组和

53. 最大子数组和 - 力扣（Leetcode）

• 题目要求子数组是连续的，可以用数组的滑动窗口的思路来思考，但这道题只需要用i控制窗口的终止位置。
• 每一步是什么：这一步枚举到的元素为nums[i]，当前子数组的和为cur。如果cur小于0，则将cur归零，从nums[i + 1]重新求和。
• 局部最优：如果当前子数组的cur比之前保存的maxSum要大，则将cur赋值给maxSum。
• 全局最优：maxSum是最大的子数组的和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int cur = 0;
        for (int i = 0; i < nums.size(); i++) {
            cur += nums[i];
            if (cur > res) res = cur;
            if (cur < 0) cur = 0;
        }
        return res;
    }
};

今日总结

• 贪心算法确实很巧妙，确实没有固定的通法或套路。贪心算法似乎就是具有贪心选择性质的问题的最优解。贪心选择性质本身就是特殊的性质，只有很少一部分问题具备，这似乎也导致了贪心法写出的代码虽然简单，但在数学上证明起来困难，也很难快速想到如何选择合适地贪心策略（即如何定义每一步和局部最优）。