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.
給定一個數(shù)組姜挺，每個元素代表當前索引位置勤揩，你能跳躍的距離，問從0索引位置開始溜徙，你是否能跳到最后一個元素。

一犀填、暴力解法蠢壹，深度優(yōu)先搜索的思路，即嘗試從位置0開始的所有跳法九巡，但是這種方法有很多的重復(fù)計算图贸，比如有n種方法都能跳到第i個位置，這個方法的時間復(fù)雜度是指數(shù)級別冕广。

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;
}

二疏日、動態(tài)規(guī)劃，對于每個位置i來說撒汉，如果它前面某個位置j可以被跳達并且這個位置的value大于等于i-j沟优，那么i也是可以被跳達的。所以對于位置i來說神凑，可以遍歷i前面的所有位置净神，只要有一個位置滿足上面的條件何吝，位置i就是可以跳到的。下面是代碼鹃唯，時間復(fù)雜度是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弟晚，時間復(fù)雜度是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;
}