康瑞部落

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

解题思路：

1、这一道题最开始想到的就是回溯法。代码如下。其中用一个标记数组来标记某个元素是否验证过。即使这样，时间复杂度也为O(n^2)，当数组很大时，仍然产生超时错误。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        if(len<=1){
            return true;
        }
        bool check[len];
        memset(check, 0, sizeof(bool)* len);
        
        return canJumpHelper(nums, check, 0);
    }
    
    bool canJumpHelper(vector<int>& nums, bool* check, int index){
        if(check[index]){
            return false;
        }
        int len = nums.size();
        if(index>=len-1){
            return true;
        }
        for(int i=nums[index]; i>0; i--){
            if(canJumpHelper(nums, check, index + i)){
                return true;
            }
        }
        check[index]=true;
        return false;
    }
};

2、动态规划算法。有一个数组contribution[len]，其中contribution[i]表示在i-1前走的方法中，到i这里还剩下最大的步数。其递推公式为：

contribution[i] = 0,   i==0
contribution[i] = max(contribution[i-1], nums[i-1]) - 1, 其他

例如，对给的例子来说，有：

2, 3, 1, 1, 4
0, 1, 2, 1, 0

到第3个元素时，其contribution[2]的值为2，表示按前面的方法走到第三个元素时，最多还剩下2步。

判断能否走到最后一步的条件是中间任何补个contribution都大于等于0且contribution[len-1]>=0。

时间复杂度为O(n)，空间复杂度为O（n）

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

3、贪心算法。用一个变量记录所有能够覆盖的最大下标。时间复杂度为O(n)，空间复杂度为O(1)

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