122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。 最大总利润为 4 + 3 = 7 。
思路
用贪心算法思路解决，不能再考虑状态的转移，而是应该考虑有哪些情况可以构建出稳赚不赔的局部最优？
因为可以多次买卖，参考昨天最大自序和的丢弃负数思想，将每一天的盈利计算出来，只在那些前后两天盈利为正的天进行买卖
代码实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for(int i=1; i<prices.size(); i++){
result += max(prices[i]-prices[i-1], 0);
}
return result;
}
};
55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
思路
每个元素只是能跳的 最大 范围，因此不用担心会有 ”先跳小才能再跳大” 的情况，只要最大范围能够覆盖终点（数组最大下标），就一定能跳跃成功
因此局部最优就是每次都跳最大（每过一个位置需要判断，当前更大就落地重新跳，当前小就延续之前接着跳），看能否超过终点下标
当然如果是求最小跳跃次数，那本题的贪心策略就被推翻了
代码实现
本题的核心在于覆盖范围 cover，不是说简单的从第一个元素遍历一遍即可，
i<nums.size()遍历，事实上是每次只跳一步，没有充分考虑该元素的整个范围i<=cover遍历，才是真正的边跳边看，每一步的跳跃范围都会随着cover实时更新
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
for(int i=0; i<=cover; i++){
cover = max(i+nums[i], cover);
if(cover >= nums.size()-1) return true;
}
return false;
}
};
45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
思路
果然这一题开始考虑最小步数了，那就不可以有多远跳多远了，
举一个反例 [4, 100, 100, 100, 1, 1, …, 1]
本质上仍是考虑最大范围，但是要 以最小的步数增加覆盖范围，因此需要同时统计这一步的最大范围和下一步的最大范围
下下一步的就无需考虑了，本质上它只取决于下一步而不是这一步
还有一种特殊情况，如果边跳边看还是到达了起跳时的最大范围，且仍不是终点，那就需要加一再向前走一步
代码实现
定义两个变量，分别记录 当前范围 和 下一步范围，
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() == 1) return 0;
int curDistance = 0; // 这一步覆盖最远下标
int nextDistance = 0; // 下一步覆盖最远下标
int ans = 0; // 步数记录
for (int i = 0; i < nums.size(); i++) {
nextDistance = max(nums[i] + i, nextDistance);
if (i == curDistance) { // 已到达当前最远下标，就前进一步
ans++;
curDistance = nextDistance;
if (nextDistance >= nums.size() - 1) break; // 这一步覆盖最远下标已到达集合终点，结束
}
}
return ans;
}
};
1005. K 次取反后最大化的数组和
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
- 选择某个下标
i并将nums[i]替换为-nums[i]。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
示例 1：
输入：nums = [3,-1,0,2], k = 3 输出：6 解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
思路
这个过程可以重复k次，但没有要求不能在同一元素上重复操作，因此贪心策略就是：
- 若存在负数，则将 绝对值 最大的负数取反
- 若已无负数，则将 绝对值 最小的正数反复取反直至
k消耗完
代码实现
本题的核心是按绝对值排序，sort函数默认按从小到大排序，可以通过在函数中增加规则函数，自定义排序的结果，其中：
a>b代表从大到小排序abs(a)代表按绝对值排序
此外 k 可以重复消耗的思想也很重要，若其为偶数，则相当于未操作；若为奇数， 相当于仅最后一次取负操作有效，直接将最小值取负即可
class Solution {
static
bool cmp(int a, int b){
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), cmp);
for(int i=0; i<nums.size(); i++){
if(nums[i]<0 && k>0){
nums[i] *= -1;
k--;
}
}
if(k%2==1) nums[nums.size()-1] *= -1;
int result = 0;
for(int num : nums) result += num;
return result;
}
};
后记
背包问题大多可以用动态规划解决，
- 背包靠的是常识和直觉（能否想出局部最优解，或者举反例驳斥局部最优）
- 动态规划靠的是固定的解题思路（同一类型的问题有固定的DP公式）
