https://leetcode-cn.com/problems/jump-game/
点击查看【bilibili】

题目

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

示例

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

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

解答

方法一：递归，动态规划

image.png

  1. 通过递归，遍历出所有的路
  2. 通过标识来标识此路是否能通（0-未知，1-通的，2-不通）
  3. 初始化每个点都是未知的，最后一个点是通的
  4. 通过递归判断每一个点，到达一个位置，
    • 如果这个位置是0的话，我们要进行判断
    • 如果这个位置是1的话，不需要判断，此位置是通的
    • 如果这个位置是-1的话，不需要判断，此位置是不通的
  5. 处理越界问题，比较 当前点能跳的步数 和 数组的最大长度，哪个最小，作为最大可跳跃数(比如[3],最大跳跃3步，但数组长度为1，所以只能跳一步)

  6. 递归遍历当前位置到最大跳跃数(也就是遍历这几条路)，

    • 如果那条路是通的，标记为1，返回true
    • 如果没有返回true，那么当前点标记为-1，返回false ```javascript var canJump = function(nums) { const totalLength = nums.length; // 初始化每个点都是未知的，最后一个点是通的 const memo = Array(totalLength).fill(0); // dp 记忆化数字 memo[totalLength - 1] = 1; // 递归遍历 function jump(position){ if(memo[position] === 1) { // 如果是1，就是通的 return true }else if(memo[position === -1]) { // 如果是-1，就是不通的 return false } // 处理越界问题 const maxJump = Math.min(position + nums[position], totalLength-1) for(let i=position+1;i<= maxJump;i++) { const jumpResult = jump(i); if(jumpResult === true) { memo[position] = 1; return true } } memo[position] = -1; return false }

    let result = jump(0) return result }; ```

    方法二：bottom-up

  7. 倒序循环，从后往前遍历

  8. 判断当前点是否可以走到1的地方

可以的话当前点就是1，不可以则是-1
一直循环到最开始的点
如果最开始的点是1，那么返回true，否则返回false

var canJump = function(nums) {
  const totalLength = nums.length;
  // 初始化每个点都是未知的，最后一个点是通的
  const memo = Array(totalLength).fill(0);
  // dp 记忆化数字
  memo[totalLength - 1] = 1;

  for(let i=totalLength-2;i >= 0; i--) {
    const maxJump = Math.min(i+nums[i], totalLength-1) 
    for(let j=i+1;j<=maxJump;j++) {
      if(memo[j] === 1) {
        memo[i] = 1
        break;
      }
    }
  }
  if(memo[0] === 1) {
    return true
  }else {
    return false
  }
};

方法三：贪心模式

image.png

  1. 定义一个变量maxJump，初始化数组长度-1
  2. 从后往前遍历
  3. 如果前一个点的值+对应的索引值 >= maxJump，那么maxJump等于当前点的索引值
  4. 直到遍历到第一个点，
    1. 如果maxJump=0，说明第一个点可以跳到最后，返回true
    2. 如果maxjump!=0，说明第一个点不可以跳到最后，返回false
      var canJump = function(nums) {
let maxJump = nums.length -1 
for(let i=nums.length-2;i>=0;i--) {
if(i+nums[i] >= maxJump) {
maxJump = i
}
}
return maxJump === 0
};