题目

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

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

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

示例 1:

1
2
3


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

示例 2:

1
2
3


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

题解

注意，下面说明中的位置从1开始，不是从0开始。

最开始的思路就是暴力遍历，首先在第一个位置上，我们知道了最大可跳跃的距离，那我们就从1开始到最大距离进行遍历，当前位置加上跳跃的距离，之后再次进行该递归操作，继续往下遍历，终止条件是当前位置加上跳跃的距离大于了数组的长度，那说明为真，如果遍历完都无法大于数组的长度，那么说明无法跳跃到终点，返回为假。

以题目给的例子2, 3, 1, 1, 4来说，首先我们在第一个位置上，可跳跃的最大距离是2，那么我们可跳1次，也可跳2次。如果跳一次，我们就在第二个位置上，可跳跃的距离是3，我们依旧可以选择跳1次，那么我们在位置3上，再跳一次，跳到位置4，再跳一次，跳到位置5，到达终点。

以例子3, 2, 1, 0, 4为例，首先我们在第一个位置上，可跳跃最大为3，我们首先跳1次，跳到位置2，再跳一次，到位置3，再跳一次，到位置4，这个时候可跳最大距离为0，无法再跳了。

那么我们回去，在位置2上，我们跳2次，又跳到了位置4，没办法继续。

我们再回头回到位置1，我们选择跳2次，跳到位置3，而我们知道位置3是不行的，那么我们返回到位置1。我们选择跳3次，跳到了位置4，没办法继续进行下去。这个时候所有的可能性都试完了，没有找到路径大于数组的长度，我们得出结论无法跳跃到终点。

这种方式复杂度肯定非常高，为了降低复杂度，需要使用一定的空间进行备份数据，进行剪枝。实现如下：

 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


bool interCanJump(int *nums, int pos, int count, map<int, bool> &backups) {
   int curr_steps = nums[pos];
   // 如果结果存在，直接返回，不再递归查找
   if (backups.find(pos) != backups.end()) {
       return backups[pos];
   }

   // 当前位置+跳跃距离大于数组长度，返回真
   if (pos + curr_steps >= count - 1) {
       backups[pos] = true;
       return true;
   }

   // 在当前位置上递归遍历所有跳跃距离
   for (int i = curr_steps; i >= 1; i--) {
       if (interCanJump(nums, pos + i, count, backups))
           return true;
   }

   backups[pos] = false;
   return false;
}

bool canJump(vector<int>& nums) {
   if (nums.empty())return false;
   map<int, bool> backups;

   return interCanJump(&nums[0], 0, nums.size(), backups);
}

但在leetcode上运行后，发现当数据特别大时，将会运行超时。显然还有更加优化的算法。

这道题实际上属于动态规划，这个时候我们就要开始想怎么往动态规划上凑。在上面的实现中，效率低的一个主要原因是我们进行了很多无效的遍历，虽然有很多重复的遍历被我们存储，但依旧有很多情况是没有必要遍历的。

我们实际需要的是在当前的位置下，我们最远可以跳到的最远距离是哪里。这依旧是个求最值的问题，即我们能够跳的最远距离是哪里？如果最远距离都不大于数组长度，那么结果肯定是假。如果大于，那么结果就是真。

那么我们想该怎么求最远的距离。

依旧以例子2, 3, 1, 1, 4来说，我们当前在位置1，这个时候我们有2种选择，要么跳1步，要么跳2步。如果跳1步，那么会到位置2，可跳跃的最大长度为3，那么如果选择跳1步，可跳的最远距离是1 + 1 + 3，我们在位置1上，跳了1步，之后又可最多跳3步，所以我们最远可跳到位置5。

如果我们在位置1上选择跳2步，那么我们到位置3，位置3的最大距离为1，那么这种情况下的最远距离是 1 + 2 + 1，结果为4，这种方式肯定显然不如第一种方式，所以我们选择第一种方式。

当我们选择第一种方式后，我们发现跳到的最大距离已经大于等于数组的长度，那么我们的结果就为真了。

再拿例子3, 2, 1, 0, 4来说，我们在位置1上，选择有3种，如果跳1次，那么在位置2，位置2上的最大距离为2，那么最大距离为：1 + 1 + 2，结果为4。

如果跳2次，那么最大距离为：1 + 2 + 1，结果依旧为4。如果跳3次，那么结果为：1 + 3 + 0，结果依旧为4。

几种方式相同，那么我们选最大的跳3次，当我们到位置4后，我们发现当前最大可跳跃距离为0，这个时候无法进行下去了，那么直接返回假。

经过上面的说明，会发现这道题实际上是个贪心，当前局部最优结果便是最终的最优结果。

代码实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


bool canJump(vector<int>& nums) {
    if (nums.empty())return false;
    
    int pos = 0;
    // 如果可跳跃距离小于数组长度就一直循环
    while (pos + nums[pos] < nums.size() - 1) {
        int tmp_pos = pos;
        int max_step = 0;
        
        // 如果可跳跃距离为0，说明没办法再前进，那么返回假
        if (nums[tmp_pos] == 0) return false;

        // 在当前位置下，查找可跳跃的最远距离，并保存对应的位置
        for (int i = 1; i <= nums[tmp_pos]; i++) {
            if (tmp_pos + i + nums[tmp_pos + i] >= max_step) {
                max_step = tmp_pos + i + nums[tmp_pos + i];
                pos = tmp_pos + i;
            }
        }
    }

    return true;
}

这种方式下，就可完成题目，不再会出现超时问题。主要原因是，我们只找可跳跃的最长的那个距离，不再像第一种方式那样，长的、短的全都尝试一遍，无用的跳跃方式太多，导致复杂度上升。

这个时候，再来看网上相关的题解，发现实际上有更简单的方法，实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


bool canJump(vector<int>& nums) {
    if (nums.empty())return false;
    
    int max_step = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (i > max_step) {
            return false;
        }

        max_step = max(nums[i] + i, max_step);
    }

    return true;
}

实际上自己实现的第二种方式已经跟这个很像了，但确实没有这个优化程度高。

这个实现的思想是，我们记录一个可以走的最远长度max_step，当我们开始往前跳时，判断我们是否在这个最远可走的范围内，如果不在，那么就返回假。

如果在，我们更新下最远可跳的位置，最远可跳的位置是max_step = max{ i + nums[i], max_step}。然后依次往前走。

再看下自己的实现，实际上所想的有点接近这个思想，找到最远可跳的位置，之后更新位置，再往前找最远可跳的位置，依次往前，判断是否可到达终点，但自己实现的复杂度太高了，水平还是有限。