代码随想录刷题day32 122.买卖股票的最佳时机II；55 _利润

代码随想录刷题day32 122.买卖股票的最佳时机II；55. 跳跃游戏；45.跳跃游戏II
贪心的进阶题目。贪心相比动态规划更加简单，但是也只能针对固定题目。
122.买卖股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣（）
思路
本题首先要清楚两点：
想获得利润至少要两天为一个交易单元。
贪心算法
这道题目可能我们只会想，选一个低的买入，在选个高的卖，在选一个低的买入…循环反复。
如果想到其实最终利润是可以分解的，那么本题就很容易了！
如何分解呢？
假如第0天买入，第3天卖出，那么利润为：[3] - [0] 。
相当于([3] - [2]) + ([2] - [1]) + ([1] - [0]) 。
此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
那么根据可以得到每天的利润序列：([i] - [i - 1])…([1] - [0]) 。
如图：
第一天当然没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！
从图中可以发现，其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。
那么只收集正利润就是贪心所贪的地方！
局部最优：收集每天的正利润，全局最优：求得最大利润。
局部最优可以推出全局最优，找不出反例，试一试贪心！
对应C++代码如下：
class Solution {public:int maxProfit(vector& prices) {int result = 0;for (int i = 1; i < prices.size(); i++) {result += max(prices[i] - prices[i - 1], 0);}return result;}};
动态规划 55. 跳跃游戏
55. 跳跃游戏 - 力扣（）
跳跃的最大范围能覆盖就返回true，否则就是false 。以为是动态规划，结果是贪心。
思路
其实跳几步无所谓，关键在于可跳的覆盖范围！
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

文章插图
这个范围内，别管是怎么跳的，反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
局部最优推出全局最优，找不出反例，试试贪心！
如图：
每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
而cover每次只取 max(该元素数值补充后的范围, cover本身范围) 。
如果cover大于等于了终点下标，直接 true就可以了。
C++代码如下：

class Solution {public:bool canJump(vector& nums) {int cover = 0;if (nums.size() == 1) return true; // 只有一个元素，就是能达到for (int i = 0; i <= cover; i++) { // 注意这里是小于等于covercover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了}return false;}};

45.跳跃游戏II
45. 跳跃游戏 II - 力扣（）
其实看的挺懵逼的，基本不知道说的什么，先记录一下吧。
【代码随想录刷题day32 122.买卖股票的最佳时机II；55】代码随想录 ()