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

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

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

示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

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

回溯法

首先想到的是暴力法，针对每个位置可能走的步数一个个进行测试，如果这个步数能到达或者超过最后一个位置说明就可以到达，写代码的过程中注意将已经计算过的缓存起来，使用记忆化搜索防止重复计算。还可以从最大可能走的步数开始减少代替自增这样的小技巧来优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var canJump = function (nums) {

  const cache = {};

  /**
   * 从i位置向后跳
   * @param i
   */
  function jump(i) {
    if (cache[i] !== void 0) return cache[i];
    // 跳到最后位置了
    if (i >= nums.length - 1) {
      return cache[i] = true;
    }
    let step = nums[i];
    if (step === 0) {
      return cache[i] = false;
    }
    if (i + step >= nums.length - 1) {
      return cache[i] = true;
    }
    while (step >= 1) {
      const flag = jump(i + step);
      if (flag) {
        return cache[i] = true;
      }
      step--;
    }
    return cache[i] = false;
  }

  return jump(0);
};

贪心法

解题思路如下：

  1. 如果某一个作为起跳点的格子可以跳跃的距离是3，那么表示后面3个格子都可以作为起跳点。
  2. 可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。
  3. 如果可以一直跳到最后，就成功了。

代码写出来非常精简，效率更是秒杀回溯法，有没有：

1
2
3
4
5
6
7
8
9
10
11
12
13
var canJump = function (nums) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > k) {
            return false;
        }
        k = Math.max(k, i + nums[i]);
        if (k >= nums.length - 1) {
            return true;
        }
    }
    return true;
};

这种方法的核心依据是：从当前位置能够到达某一个位置，那么从当前位置都可以到达某一位置左侧的所有位置。因此我们每次算的时候直接尝试最大步数就行了.例如nums[i] == 3，我们就不需要计算走一步，走两步了。

举个例子：如果从位置 3 可以跳到 位置 8，那么中间的 4、5、6、7 都可到达， 但是如果遇到下一个位置 i ，超过了目前可跳的最远距离 k ，那么直接返回 false 即可， 因为 i 位置左侧可跳的最远距离 k 都到达不了下一个位置 i，那么 i 和 i 后面的 位置皆不可到达。