跳跃游戏

能否到达终点怎么用 dp 表示？

• 问题: 每个位置的值是最大跳跃长度, 判断能否从 0 跳到末尾 (55);
• 状态: dp[i] 为从位置 0 出发能跳出的最远距离;
• 转移:
  • 若 dp[i-1] >= i, 说明能到达位置 i, 可以起跳: dp[i] = max(dp[i-1], i + nums[i]);
  • 否则位置 i 不可达, 最远距离不变: dp[i] = dp[i-1];
• 初值: dp[0] = nums[0];
• 答案: dp[n-1] >= n-1;

const canJump = (nums) => {
  const n = nums.length;
  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
  for (let i = 1; i < n; i++) {
    dp[i] = dp[i - 1] >= i ? Math.max(dp[i - 1], nums[i] + i) : dp[i - 1];
  }
  return dp[n - 1] >= n - 1;
};

• 优化: 只需维护一个"当前最远可达位置"变量, 时间从 O(n) 状态变为原地滚动, 空间 O(1);

最少步数怎么用 dp 表示？

• 问题: 求跳到末尾的最少跳跃次数 (45);
• 状态: dp[i] 为从 0 到位置 i 的最少步骤;
• 转移: 枚举所有能跳到 i 的位置 j, 取最小步骤加一;
  • 条件: j + nums[j] >= i;
  • 方程: dp[i] = min(dp[i], dp[j] + 1);
• 初值: dp 全部填 Infinity, dp[0] = 0;
• 答案: dp[n-1];
• 复杂度: 时间 O(n^2), 空间 O(n);

const jump = (nums) => {
  const n = nums.length;
  const dp = new Array(n).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (j + nums[j] >= i) dp[i] = Math.min(dp[i], dp[j] + 1);
    }
  }
  return dp[n - 1];
};