摘要
- 贪心算法可以认为是动态规划算法的特例。对于可能具有贪心选择性质的问题，可以先尝试贪心算法，看运行结果是否正确，贪心算法不对则退一步，用动态规划求解。
- 或许应该先复习动态规划再复习贪心算法，贪心算法太巧妙了，如果没有选择正确的贪心策略，还是很难解决问题的。
贪心算法理论基础
1. 和动态规划的关系
- 贪心算法可以认为是动态规划算法的特例，和动态规划相比，使用贪心算法解题需要问题满足额外的条件（即贪心选择性质）
2. 贪心选择性质
2.1 概念
- 贪心选择性质，直观地去理解，就是每一步都做出一个局部最优的选择，逐步的局部最优直到最终的结果是全局最优。
- 这是一个特殊的性质，只有一部分问题满足这个性质。
2.2 要不要证明？
- 贪心选择性质的判断和证明目前还没有简单的通法，一般可以通过数学归纳法和反证法来进行严谨的数学证明，但耗时较长，相对于解题时间来说得不偿失。和严谨地证明贪心选择性质相比，直接尝试贪心算法，看最终结果是否正确，或者能不能举出反例来说明不能用贪心效率更高。
- 对于可能具有贪心选择性质的问题，可以先尝试贪心算法，贪心算法不正确再退一步使用动态规划。
2.3 贪心算法的思考步骤
从贪心选择性质的概念出发，每一步的局部最优最终导致全局最优。在解决一个具体问题是，这需要我们明确以下三步：
- 每一步（即子问题）是什么，如何把问题分解成子问题，或者说模拟求解的过程中如何定义“一步”怎么走。
- 这一步的局部最优是什么
- 全局最优是什么
- 最后再尽量用一句话来总结贪心选择的过程
贪心算法确实没有固定的模板或者套路，但形成一套自己的方法论还是有必要的，不能漫无目的的思考。
LeetCode455 分发饼干
- 每一步是什么：把一块饼干
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 摆动序列
- 先考虑边界条件，题目说“仅有一个元素或者含两个不等元素的序列也视作摆动序列”，那先过滤掉只有一个元素的情况。
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 最大子数组和
- 题目要求子数组是连续的，可以用数组的滑动窗口的思路来思考，但这道题只需要用
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;
}
};
今日总结
- 贪心算法确实很巧妙，确实没有固定的通法或套路。贪心算法似乎就是具有贪心选择性质的问题的最优解。贪心选择性质本身就是特殊的性质，只有很少一部分问题具备，这似乎也导致了贪心法写出的代码虽然简单，但在数学上证明起来困难，也很难快速想到如何选择合适地贪心策略（即如何定义每一步和局部最优）。
