LeetCode: 跳跃游戏

[HeyShinner]

https://leetcode-cn.com/problems/jump-game/

[HeyShinner]

• 时间复杂度计算

[HeyShinner]

• 方法一：回溯

var canJump = function(nums) {
  return canJumpFromPos(0, nums);
};

function canJumpFromPos(pos, nums) {
    if (pos === nums.length - 1) {
      return true;
    }
    let furtherJump = Math.min(pos + nums[pos], nums.length - 1);
    for (let nextPos = furtherJump; nextPos > pos; nextPos --) {
      if (canJumpFromPos(nextPos, nums)) {
        return true;
      }
    }
    return false;
  }

时间复杂度为什么是 O(2^n)

• 方法二：自顶向下的动态规划

var canJump = function(nums) {
  const memo = new Array(nums.length);
  for (let i = 0; i < memo.length; i ++) {
    memo[i] = 'unkonwn';
  }
  memo[memo.length - 1] = 'good';
  
  const canJumpFromPos = (pos, nums) => {
    if (memo[pos] !== 'unkonwn') {
      return memo[pos] === 'good' ? true : false;
    }
    let furtherJump = Math.min(pos + nums[pos], nums.length - 1);
    for (let nextPos = furtherJump; nextPos > pos; nextPos --) {
      if (canJumpFromPos(nextPos, nums)) {
        memo[pos] = 'good';
        return true;
      }
    }
    memo[pos] = 'bad';
    return false;
  }

  return canJumpFromPos(0, nums);
};

时间复杂度 O(n^2)

• 自底向上的动态规划
• 贪心