一开始用bfs做，memory不够，估计用dfs可以做。既然可以dfs来做，而且不需要保存路径等信息，肯定可以用dp来做。

 

方法一：DP

时间复杂度O(n^2)

class Solution {public:    bool canJump(vector
     
      & nums) {        vector
      
        dp(nums.size(),false);        dp[0] = true;                for (int i=0;i
      
     

 

方法二：Greedy

久违的贪心问题，其实我们只关心最大能跳到的距离， 因此可以用贪心来做。

时间复杂度O(n)

class Solution {public:    bool canJump(vector
     
      & nums) {        int max_index=0;        for (int i=0;i
      
       max_index) return false;            if (i+nums[i]>max_index){                max_index = max(max_index,i+nums[i]);                if (max_index>=nums.size()-1) return true;            }        }        return max_index>=nums.size()-1;    }};
      
     

 

45. Jump Game II

用DP竟然超时了 = =

class Solution {public:    int jump(vector
     
      & nums) {        vector
      
        dp(nums.size(),INT_MAX);        dp[0] = 0;        for (int i=0;i
      
     

 

只能用贪心做，但是不能简单的选择最大的。

如果当前能到达的范围为 [start, end]，那么在这个范围内寻找能够调到最远的下标 max_end，那么跳跃以后新的范围就变成了 [end+1, max_end]

下面代码里start是多余的，而且还需要注意，循环里 i<nums.size()-1，因为i==nums.size()的时候

class Solution {public:    int jump(vector
     
      & nums) {        int cnt=0;        int start=0, end=0, max_end=0;                // cur scope is [start,end], then will be [end+1,max_end]        for (int i=0;i
      
       end) return -1;            max_end = max(max_end,i+nums[i]); //update the max_end that can be reached by cur scope            if (i==end){ // jump to a new scope                start = end+1;                end = max_end;                ++cnt;                //if (end>=nums.size()-1) break;            }        }        return cnt;    }};
      
     

 

另一种写法，思路是一样的

class Solution {public:    int jump(vector
     
      & nums) {        int cnt=0;        int start=0, end=0;                // cur scope is [start,end], then will be [end+1,max_end]        while (end
      
       =nums.size()-1) return cnt;                max_end = max(max_end, i+nums[i]);            }            start = end+1;            end = max_end;        }        return cnt;    }};