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.
给定一个数组，每个元素代表当前索引位置，你能跳跃的距离，问从0索引位置开始，你是否能跳到最后一个元素。

一、暴力解法，深度优先搜索的思路，即尝试从位置0开始的所有跳法，但是这种方法有很多的重复计算，比如有n种方法都能跳到第i个位置，这个方法的时间复杂度是指数级别。

public boolean canJump1(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return true;
    }

    return helper(nums, 0);
}

public boolean helper(int[] nums, int index) {
    if (index == nums.length - 1) {
        return true;
    }

    int maxJump = nums[index];
    for (int i = index + 1; i <= index + maxJump; i++) {
        if (helper(nums, i)) {
            return true;
        }
    }

    return false;
}

二、动态规划，对于每个位置i来说，如果它前面某个位置j可以被跳达并且这个位置的value大于等于i-j，那么i也是可以被跳达的。所以对于位置i来说，可以遍历i前面的所有位置，只要有一个位置满足上面的条件，位置i就是可以跳到的。下面是代码，时间复杂度是n方，很可惜，leetcode居然提示超时。

public boolean canJump(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return true;
    }
    
    int n = nums.length;
    boolean[] dp = new boolean[n];
    dp[0] = true;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && nums[j] >= i - j) {
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[n - 1];
}

三、贪心算法，贪心我觉得挺难想的，因为每道题贪心的思路都不一样，下面就仅展示一下代码吧。思路就是维持一个lastPos，如果前面某个点能跳到lastPos，就把lastPos更新为这个点，最后看lastPos是否是0，时间复杂度是n。

public boolean canJump(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return true;
    }
    
    int lastPos = nums.length - 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        if (nums[i] + i >= lastPos) {
            lastPos = i;
        }
    }
    
    return lastPos == 0;
}