55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

反向查找，动态规划。
到达目标点前必须到达上一个节点，且上一个节点能前进的步数必须大于目标点。
设置目标点goal，反向遍历goal以外的点。
如果该点能前进的步数加上自身的位置i大于目标点，则可以从上一个点到达goal。
更新goal的位置到上一个点。
如果遍历结束后，能返回到起始点0，则可以到达终点。

class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length-1;
        for(int i = nums.length-2; i >=0; i--){
            if(nums[i] >= goal - i) goal = i;
        }
        return goal == 0;
    }
}

贪心算法，储存一个到i时可以到达的最远值maxJump。
遍历数组，如果i大于maxJump，则无法到达下一个点，返回false。
在当前点可以到达的最大范围为nums[i]+i，如果大于maxJump则更新该值。
遍历完毕返回true。

class Solution {
    public boolean canJump(int[] nums) {
        int maxJump = 0;
        for(int i = 0; i < nums.length; i++){
            if(i > maxJump) return false;
            maxJump = Math.max(maxJump, nums[i] + i);
        }
        return maxJump >= nums.length-1;
    }
}

设置一个数组记录可访问的范围。
当遍历时，如果可以访问，则将当前位置可以进一步访问的位置变为1。
如果访问范围大于等于数组末尾，则返回真。

class Solution {
    public boolean canJump(int[] nums) {
        int[] reach = new int[nums.length];
        reach[0] = 1;
        
        for(int i = 0; i < nums.length; i++){
            if(reach[i] == 1){
                if(i == nums.length-1) return true;
                for(int j = 0; j < nums[i]; j++){
                    if(i+j+1 >= nums.length) return true;
                    reach[i+j+1] = 1;
                }
            }
        }
        return false;
    }
}