Jump Game(Medium)

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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

Solution

class Solution {
    private boolean find=false;
    public boolean canJump(int[] nums) { 
        /*
        if(nums==null) return false;
        
        int index=0;
        dfs(nums,index);
        return find;
        */
        if(nums==null) return false;
        /*
        int reach=0,n=nums.length;
        for(int i=0;i<=reach;i++){
            if(i+nums[i]>reach) reach=i+nums[i];
            if(reach>=n-1) return true;
        }
        */
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
        return false;
    }
    /*
    private void dfs(int[] nums,int i){
        
        if(find){
            return;
        }
        if(i>=nums.length){
            return;
        }
        if(i==nums.length-1){
            find=true;
            return;
        }
        for(int j=nums[i];j>0;j--){
            dfs(nums,i+j);
        }
        
    }
    */
}

时间O(n)
空间O(1)

我只能想到回溯法，如我所料，超时了。
贪心法是最优算法，从后往前看，如果它的值加上它的位置超过了最后一个位置，动态更新最后一个位置到当前位置，依次往前递推。最后判断最后一个位置是不是初始位置0就可以了