题目

题目来源：力扣（LeetCode）

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

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

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

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

思路分析

  1. 状态dp，初始化为全false（true表示能到达，false表示无法到达）
  2. dp[0] = true，第一个点一定能走到
  3. 接下来考虑第二个点开始判断能否到达该点？
    • 想知道能否到达该点，则要看能否从该点之前的点跳跃过来，从后往前找的原因是越接近它的点 越可能能够跳 过来，可以减少循环次数
    • 如果前面有的点到达不了，就不必考虑从那个点跳不跳的过来了，因为那个点自己本身都到不了
    • 如果找到了可以跳到当前点的前面的点，则当前点可达到，更新他的状态为true，并退出循环
  1. /**
  2.  * @param {number[]} nums
  3.  * @return {boolean}
  4.  */
  5. var canJump = function (nums) {
  6.   //特殊情况只有一个元素
  7.   if (nums.length == 1) return true
  8.   //状态dp，初始化为全false（true表示能到达，false表示无法到达）
  9.   const dp = new Array(nums.length).fill(false)
  10.   //第一个点一定能走到
  11.   dp[0] = true
  12.   //从第二个点开始判断能否到达该点？
  13.   for (let i = 1; i < nums.length; ++i) {
  14.     //想知道能否到达该点，则要看能否从该点之前的点跳跃过来，从后往前找的原因是越接近它的点越可能能够跳过来，可以减少循环次数
  15.     for (let j = i - 1; j >= 0; --j) {
  16.       //如果前面有的点到达不了，就不必考虑从那个点跳不跳的过来了，因为那个点自己本身都到不了
  17.       if (!dp[j]) continue
  18.       //如果前面有点能达到，但是跳不了足够远到此点，也继续找再往前一个点
  19.       if (nums[j] < i - j) continue
  20.       //如果找到了可以跳到当前点的前面的点，则当前点可达到，更新他的状态为true，并退出循环
  21.       dp[i] = true
  22.       break
  23.     }
  24.   }
  25.   //返回最后一个点是否能达到
  26.   return dp[nums.length - 1]
  27. };