理论基础
贪心问题，本质是 选择每一阶段的局部最优，从而达到全局最优 。
例如从一堆珠宝中自由拿取，那么每次都拿价值最大的一定能达到最终的最优数额。但是假如有背包容量的限制，此时一味选择价值最大的就不再有效，此时就需要动态规划。
因此判断何时可以使用贪心算法，最好的方法就是举反例，能否想出一个局部最优无法推出全局最优的反例（从10车煤矿和10条金项链选10次，单车煤矿价值更高但最多只能拿走一车），如果不能，就可以用贪心问题求解。
其实贪心求解更倾向于常识性的推理，本能的去这么做。但如果要建模出一个解题步骤，可以如下：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i] 这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j分配给孩子i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。
思路
应该避免饼干的浪费，使得每一个饼干都能尽可能满足胃口更大的，因此这里的局部最优就是将大饼干喂给胃口大的，从而实现全局最优——喂饱尽可能多的小孩
代码实现
用大饼干优先满足大胃口，因此排序后，自后向前逐个比较饼干和小孩，小孩不被满足则跳过前移（即使当前最大的饼干也无法满足），而饼干不能浪费，只有匹配上才会前移：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int index = s.size()-1; // 饼干指针
int result = 0;
for(int i=g.size()-1; i>=0; i--){ // 小孩指针
if(index>=0 && s[index]>=g[i]){
result++;
index--;
}
}
return result;
}
};
376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 ** 摆动序列 。** 第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。 - 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 **的 **最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
思路
暂且不看！！！
代码实现
class Solution {
public:
int dp[1005][2];
int wiggleMaxLength(vector<int>& nums) {
memset(dp, 0, sizeof dp);
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < nums.size(); ++i) {
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
}
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
}
}
return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
}
};
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
思路
此处贪心的局部最优，就是当前“连续和”为负数的时候便立刻放弃，从下一个元素重新计算，因为负数只会拉低总和
代码实现
代码实现上，从头开始用 count 累积总和，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int count = 0;
int result = INT32_MIN;
for(int i=0; i<nums.size(); i++){
count += nums[i];
if(count>result) result = count;
if(count<=0) count = 0;
}
return result;
}
};
1.要分析清楚所需变量，除了统计当前和，还要统计全局累积最大值 2.要注意结果遍历result不能为0，如果数组全为负必定会出错
后记
背包问题大多可以用动态规划解决，
- 背包靠的是常识和直觉（能否想出局部最优解，或者举反例驳斥局部最优）
- 动态规划靠的是固定的解题思路（同一类型的问题有固定的DP公式）
