跳跃游戏 II
Jump Game II
从下标 0 跳到最后一个下标，每次最多跳 nums[i] 步，求最少跳跃次数。
在力扣中练习题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i]且i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2。 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 题目保证可以到达
n - 1
解题思路
贪心 · 按层扩展
当前跳数能覆盖一层，扫描这一层找出下一层的最远边界
把跳跃看成 BFS 分层：跳 0 次能到 {0}，跳 1 次能到 0 能覆盖的范围，跳 2 次能到下一层……最少跳数就是第一次覆盖到终点的层数。
不需要真的建图，维护三个量即可：
end：当前跳数能到达的最远位置；farthest：扫描当前层时，下一跳能到达的最远位置；jumps：已经跳了几次。
从下标 0 出发，跳数 0；扫描当前层能覆盖的所有位置，找出下一层最远能到哪。
遍历 0 .. n-2，不断用 i + nums[i] 更新 farthest；当 i == end 时，当前层扫描完，跳数加一，end 更新为 farthest。
i=2，从 1 最远到 3，farthest 5 → 5；到达当前层边界，跳数 +1，下一层 end=5。
- jumps
- 2
- end
- 5
自拟数组第一层覆盖到下标 2，第二层覆盖到 5，第三层越过末尾，共 3 跳。贪心之所以正确，是因为同一层内所有位置跳数相同，只需关心最远能扩到哪。
时间 O(n)，空间 O(1)。
易错点
- 循环写到 n-1：最后一个位置不需要再起跳，可能多算一跳。
- 把 end 和 farthest 混成一个变量：无法区分“当前层边界”和“下一层边界”。
- 每次跳到当前能到的最远点：这是局部最优，但不一定保证全局最少跳数。
动态规划 · 从每个位置更新
dp[i] 表示到达 i 的最少跳数
结果正确，但 O(n²) 且需要 O(n) 数组；贪心版把状态压成三个变量。
定义 dp[i] 为到达下标 i 的最少跳跃次数，dp[0]=0。从每个可达位置 i 出发，枚举能跳到的 i+step，用 dp[i]+1 更新它们。
这是最直观的 BFS/DP 写法，正确性很容易证明；但每个位置都可能向后枚举 nums[i] 个位置，最坏 O(n²)。
它适合用来验证贪心结果，或者在跳跃规则更复杂（例如有代价、有障碍）时作为通用解法。
- 1dp[0]=0，其余为无穷大。
- 2遍历每个位置，枚举能跳到的位置。
- 3用 dp[i]+1 更新目标位置。
- 4返回 dp[n-1]。
易错点
- dp 初始化为 0：所有位置看起来都可达且跳数为 0。
- 从不可达位置继续扩展：会传播错误状态。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [2,4,1,2,3,1,2]从下标 0 出发，跳数 0；扫描当前层能覆盖的所有位置，找出下一层最远能到哪。
查看 C++ 代码
延伸阅读
- 最少跳跃、最少步数这类“每步覆盖一个区间”的问题，通常都能转成 BFS 分层，再用 end/farthest 压成 O(1) 空间。
- 第 55 题只问能否到达，维护一个 maxReach 即可；本题问最少步数，需要额外记录层边界。