class Solution {
public:
    bool backtraking(vector<int>& nums  , int target ,int step)
    {
        if (step == target) return 1; //检验步子能否到达最后点
        else if (step > target) return 0;
        if(nums[step]==0) return 0;
        for(int j=nums[step] ; j >= 1; j--)
        {
            if(backtraking(nums ,target , step + j )) return 1; 
        }
        return 0;
    }
    bool canJump(vector<int>& nums) {
        int target = nums.size() - 1;
        int step = 0;
        return backtraking(nums,target,step);
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover=0;
        for(int i=0 ; i<nums.size()-1 && i <= cover ; i++) //循环点，保证点是覆盖范围内的
        {
            if(i+nums[i] > cover ) cover = i+nums[i]; //如果当前点的范围大于现在范围，范围更新
        }
        if(cover >= nums.size()-1) return 1;   //如果范围覆盖最后一个点返回成功
        else return 0;
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int right=0;
        for(int left=0 ; left<nums.size()&&left<=right;left++)
        {
            if(nums[left]+left > right) right=nums[left]+left;
        }
        if(right >= nums.size()-1) return true;
        else return false;
    }
};