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

122.买卖股票的最佳时机II  

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

（）

代码随想录P

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

（）

Python:

class Solution:    def maxProfit(self, prices: List[int]) -> int:        if len(prices) 0:                maxProfit += curProfit            if curProfit   
C++:
  
class Solution {public:    int maxProfit(vector& prices) {        if (prices.size()     
55. 跳跃游戏 
     
本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解 
   
代码随想录
       
关键思路：
   
其实跳几步无所谓，关键在于可跳的覆盖范围！
   
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
   
这个范围内，别管是怎么跳的，反正一定可以跳过来。
    
Python:
  
Python不支持动态修改for循环中的变量。注意和C++版本的对比。
  
class Solution:    def canJump(self, nums: List[int]) -> bool:        if len(nums)==1: return True        cover = 0        for i in range(len(nums)):            if i= len(nums)-1:                    return True                    return False
  
C++:
  
class Solution {public:    bool canJump(vector& nums) {        if (nums.size()==1) return true;        int cover = 0;        for (int i=0; i= 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 0        cur_cover = next_cover = 0        ans = 0        for i in range(n):            next_cover = max(nums[i]+i, next_cover)            if i==cur_cover:                ans += 1                cur_cover = next_cover                if next_cover >= n-1:                    break        return ans

  C++:

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