55.跳跃游戏.md

55.跳跃游戏

/*
 * @lc app=leetcode.cn id=55 lang=typescript
 *
 * [55] 跳跃游戏
 */

// @lc code=start
function canJump(nums: number[]): boolean {}
// @lc code=end

解法 1: 贪心

• 时间复杂度:
• 空间复杂度:

从后往前贪心

function canJump(nums: number[]): boolean {
  let j = nums.length - 1
  for (let i = j - 1; i >= 0; i--) {
    if (nums[i] >= j - i) j = i
  }
  return j === 0
}

解法 2: 动态规划

• 时间复杂度:
• 空间复杂度:

1. 子问题: 第 i 个数字时,能跳的最远距离
2. 状态:
   • dp[i]: 第 i 个数字能跳的最远距离
3. DP 方程:
   • dp[i] = max(nums[i]+i,dp[i-1])
4. 边界:
   • dp[0] = nums[0]

function canJump(nums: number[]): boolean {
  const dp: number[] = []
  for (let i = 0; i < nums.length - 1; i++) {
    dp[i] = Math.max(dp[i - 1] ?? 0, i + nums[i])
    if (dp[i] === i) return false
  }
  return true
}

动态规划 - 优化空间

• 时间复杂度:
• 空间复杂度:

dp[i] 只跟 dp[i-1] 有关,可以只用一个变量来保存状态

其实就变成 从前往后 贪心

function canJump(nums: number[]): boolean {
  let max = 0
  for (let i = 0; i < nums.length - 1; i++) {
    max = Math.max(max, i + nums[i])
    if (max === i) return false
  }
  return true
}

Case

test.each([
  { input: { nums: [2, 3, 1, 1, 4] }, output: true },
  { input: { nums: [3, 2, 1, 0, 4] }, output: false },
  { input: { nums: [0, 1] }, output: false },
  { input: { nums: [0] }, output: true },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(canJump(nums)).toBe(output)
})