题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1：

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

回溯法思路

1.既然是判断是否可以从起点跳到最后一个位置，我们可以利用回溯算法，从起点开始将每个位置的可能性都列出来，若有其中一种路径可以跳到最终位置，那便是可以。
2.但是这是暴力求解，时间复杂度过高。

回溯法Java代码实现

public boolean canJump(int[] nums) {
        return jumpBackTrace(nums,0);
}
public boolean jumpBackTrace(int[] nums,int curPos){
        if(curPos == nums.length-1)
            return true;

        int largetestPos = Math.min(curPos+nums[curPos],nums.length-1);

        for (int i = curPos+1; i <=largetestPos ; i++) {
            if(jumpBackTrace(nums,i))
                return true;
        }

        return false;
 }

备忘录式回溯法思路

1.大体思路和回溯法相同，不同的是我们可以添加一个记事本，记录那些回溯过程中无法到达最终位置的坐标，等下次回溯到该坐标时，直接返回就可以了。
2.时间复杂度也很高，但是可以勉强通过所有用例。

Java代码实现

 enum RES{
      UNKNOWN,ERROR,RIGHT
 }

 RES[] jumpRes;

 public boolean canJump(int[] nums) {
        jumpRes = new RES[nums.length];
        for (int i = 0; i < nums.length-1; i++) {
            jumpRes[i] = RES.UNKNOWN;
        }
        jumpRes[nums.length-1] = RES.RIGHT;
        return jumpBackTrace(nums,0);
  }

 private boolean jumpBackTrace(int[] nums,int curPos){
        if(jumpRes[curPos] != RES.UNKNOWN){
            return jumpRes[curPos] == RES.RIGHT?true:false;
        }

        int jumpMax = Math.min(curPos+nums[curPos],nums.length-1);

        for (int i = curPos+1; i <= jumpMax ; i++) {
            if(jumpBackTrace(nums,i)){
                return true;
            }
        }
        jumpRes[curPos] = RES.ERROR;
        return false;
}

动态规划思路

1.其实备忘录式回溯就是自顶向下的动态规划，我们可以进一步推导出自底向上的动态规划算法，从最后一个位置往回跳，并记录跳跃后的结果，从而得出第一个位置是否可以跳到最后一个位置。
2.时间复杂度为O(n^2)，但运行时间相比前一种方法快了一些。

Java解法

  enum RES{
          UNKNOWN,ERROR,RIGHT
  }

  RES[] jumpRes;

  public boolean canJump(int[] nums) {
        jumpRes = new RES[nums.length];
        for (int i = 0; i < nums.length - 1; i++) {
            jumpRes[i] = RES.UNKNOWN;
        }
        jumpRes[nums.length - 1] = RES.RIGHT;

        for (int i = nums.length-2; i >=0 ; i--) {
            int jumpMax = Math.min(i+nums[i],nums.length-1);
            for (int j = i+1; j <= jumpMax ; j++) {
                if(jumpRes[j] == RES.RIGHT){
                    jumpRes[i] = RES.RIGHT;
                    break;
                }
            }
        }

        return jumpRes[0] == RES.RIGHT;
  }

贪心算法思路

1.通过动态规划发现，我们可以从终点往回跳，所以每次只要检测该位置是否可能直接跳到最近的可行地点便可以了；因此我们可以使用贪心算法，每次都跳最远的距离，看看是否可以到达最近的可行地点。
2.时间复杂度为O(n)，运行时间非常理想。

Java代码实现

  public boolean canJump(int[] nums) {
        int minPos = nums.length-1;
        for (int i = nums.length-1; i >= 0; i--) {
            if(i+nums[i] >= minPos){
                minPos = i;
            }
        }
        return minPos == 0;
  }

Golang代码实现

func canJump(nums []int) bool {
    latest := len(nums)-1

    for i:=len(nums)-2;i>=0;i--{
        if nums[i]+i >= latest{
            latest = i
        }
    }

    return latest == 0
}