55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

解法一 动态规划

class Solution {
    enum Index{GOOD,BAD,UNKNOWN};
    vector<Index> memo;
public:
    bool canJump(vector<int>& nums) {
        memo=vector<Index>(nums.size(),UNKNOWN);
        memo[nums.size()-1]=GOOD;

        for(int i=nums.size()-2;i>=0;i--){
            int furthestJumpFromPosition=min(nums[i]+i,(int)nums.size()-1);
            for(int j=i+1;j<=furthestJumpFromPosition;j++){
                if(memo[j]==GOOD){
                    memo[i]=GOOD;
                    break;
                }
            }
        }

        return memo[0]==GOOD;
    }
};

解法二 贪心算法

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int lastPos = nums.size() - 1;
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }

        return lastPos == 0;
    }
};