算法D32 | 贪心算法2 | 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

本题解法很巧妙，大家可以看题思考一下，在看题解。 

代码随想录P

只收集每天的正利润，利润可以每天分解。

Python:

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices)<2: return 0maxProfit = 0curProfit = 0for i in range(1, len(prices)):curProfit = prices[i] - prices[i-1]if curProfit > 0:maxProfit += curProfitif curProfit < 0:curProfit = 0return maxProfit

C++:

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() < 2) return 0;int maxProfit = 0;int curProfit = 0;for (int i=1; i<prices.size(); i++) {curProfit = prices[i] - prices[i-1];if (curProfit > 0) maxProfit += curProfit;if (curProfit < 0) curProfit = 0;}return maxProfit;}
};

55. 跳跃游戏 

本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解 

代码随想录

关键思路：

其实跳几步无所谓，关键在于可跳的覆盖范围！

不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

这个范围内，别管是怎么跳的，反正一定可以跳过来。

Python:

Python不支持动态修改for循环中的变量。注意和C++版本的对比。

class Solution:def canJump(self, nums: List[int]) -> bool:if len(nums)==1: return Truecover = 0for i in range(len(nums)):if i<=cover:cover = max(i+nums[i], cover)if cover >= len(nums)-1:return True            return False

C++:

class Solution {
public:bool canJump(vector<int>& nums) {if (nums.size()==1) return true;int cover = 0;for (int i=0; i<=cover; i++) { // for循环里的cover是动态修改的cover = max(nums[i]+i, cover);if (cover >= nums.size()-1) return true;}return false; }
};

45.跳跃游戏II 

本题同样不容易想出来。贪心就是这样，有的时候 会感觉简单到离谱，有时候，难的不行，主要是不容易想到。

代码随想录

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。

整体最优：一步尽可能多走，从而达到最少步数。

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！

移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。

这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

• 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
• 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

Python:

class Solution:def jump(self, nums: List[int]) -> int:n = len(nums)if n==1: return 0cur_cover = next_cover = 0ans = 0for i in range(n):next_cover = max(nums[i]+i, next_cover)if i==cur_cover:ans += 1cur_cover = next_coverif next_cover >= n-1:breakreturn ans

C++:

class Solution {
public:int jump(vector<int>& nums) {if (nums.size()==1) return 0;int curCover = 0;int nextCover = 0;int ans = 0;for (int i=0; i<nums.size(); i++) {nextCover = max(nums[i]+i, nextCover);if (i==curCover) {ans++;curCover = nextCover;if (nextCover>=nums.size()-1) break;}}return ans;}
};