代码随想录算法训练营第三十二天 | 122.买卖股票的最佳时机II ，55. 跳跃游戏， 45.跳跃游戏II

在这里插入图片描述
贪心：只要把每一个上升区间都吃到手，就能一直赚

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;

        for(int i = 1;i< prices.size();i++){
            int diff = prices[i] - prices[i-1];
            if(prices[i] > prices[i-1]){
               res += diff;
            }
        }
        return res;
    }
};

在这里插入图片描述
我用的是类似dp递推的解法，也就是说从出发点跳到某个位置的最小步数，来自于从出发点跳到前面这些前驱的最小步数+1，但是这个办法每一轮都要查看前面所有节点，因为节点跳跃值是不确定的，O(n^2)

class Solution {
public:
    vector<int> dp;
    void resInit(vector<int>& nums){
         vector<int> dpTem(nums.size(),INT_MAX);
         dp = dpTem;
    }
    int jump(vector<int>& nums) {
        resInit(nums);
        dp[0] = 0;
        for(int i = 1;i< nums.size();i++){
            for(int j = i-1;j>= 0;j--){
                if(dp[j] == INT_MAX){
                   continue;
                }
               if(j + nums[j] >= i){
                   dp[i] = min(dp[j] + 1,dp[i]);
               }
            }     
        }
        return dp[nums.size()-1];
    }
};

实际上，好的解法应该是一个类似于覆盖问题的做法，也就是说，第一步在第零步的基础上跳出，找出第一步的范围，如果还没到，就在第一步的基础上找第二步得得范围，，这就是一个O(n)
在这里插入图片描述

在这里插入图片描述
这道题其实也可以用一点递推的思路来做，从后往前，查找离出发点index = 0更近的 “可以到达终点的位置”，只是求一条可行通路，不用管开销，就可以这样硬推

class Solution {
public:
    vector<bool> dp;
    void resInit(vector<int>& nums){
         vector<bool> dpTem(nums.size(),false);
         dp = dpTem;
         dp[nums.size()-1] = true;
    }
    bool canJump(vector<int>& nums) {
         resInit(nums);
         int nextIdx = nums.size()-1;
         for(int i = nums.size()-2;i >= 0;i--){
            if(nums[i] + i >= nextIdx){
               dp[i] = true;
               nextIdx = i;
            }
         }
         return dp[0];
    }
};