跳跃游戏 II：从“接力赛”到“BFS 层级覆盖”——贪心 + BFS 的经典范式
【学习记录】跳跃游戏 II：从“接力赛”到“BFS 层级覆盖”——贪心 + BFS 的经典范式
在学习了“两数之和”中用哈希表记录历史状态的思维之后，我们来到了另一个完全不同的领地——贪心算法与 BFS（广度优先搜索）。如果说两数之和是“用空间换时间”的典范，那么跳跃游戏 II（LeetCode 45）则是“用策略剪枝”的教科书案例。它不再关心“谁和谁配对”，而是关心“从起点到终点的最短路程”以及“每一步如何最大化自己的覆盖范围”。今天，我们用“接力赛”的比喻，把这道题彻底拆透，并连接到大模型时代的“搜索效率”与“剪枝策略”。
📌 目录
- 题目描述
- 从熟悉到陌生：接力赛的比喻
- 核心概念解析（三层递进）
- 3.1 直觉层：为什么每一步都要“贪心”？
- 3.2 机制层：代码执行时的“时间切片”
- 3.3 本质层：BFS 层级覆盖的数学逻辑
- 关键洞察（3个最重要的细节）
- 代码实现（Python）
- 图解示例
- 复杂度分析
- 面试考点与注意事项
- 知识图谱扩展：跳跃游戏与大模型搜索策略
- 三句话带走
- 留给你的思考题
一、题目描述
给定一个长度为n的非负整数数组nums。你最初位于数组的第一个位置（下标0）。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。
示例：
输入：nums = [2, 3, 1, 1, 4] 输出：2 解释：跳到最后一个位置的最少跳跃次数是 2。 从下标 0 跳到下标 1（步长 1），然后从下标 1 跳 3 步到最后一个位置。 输入：nums = [2, 3, 0, 1, 4] 输出：2二、从熟悉到陌生：接力赛的比喻
想象你在参加一场特殊的接力赛。赛道上有许多个接力点（数组的每个下标），每个接力点都有一个牌子，上面写着：“从这里出发，最多能向前跑多少米”（nums[i]）。
你的任务：用最少的接力次数，从起点跑到终点。
直觉策略：在每一棒中，你不是随便选一个接力点就停，而是选择“在当前这一棒能覆盖的所有接力点中，选择能让下一棒跑得最远的那个点”。
举个例子（nums = [2, 3, 1, 1, 4]）：
- 起点是
0，能跑2步，覆盖[1, 2]。 - 在
1号位能跑3步（覆盖[2, 3, 4]，直接到终点），在2号位只能跑1步。 - 所以这一棒的最佳选择是跳到
1号位。 - 从
1号位出发，跑3步，直接到达终点。
核心转变：我们不是在每一棒都“跳到最远距离”，而是“跳到能覆盖最远距离的那个位置”——这正是贪心的精髓：局部最优选择 → 全局最优解。
三、核心概念解析（三层递进）
3.1 直觉层（Why）：为什么每一步都要“贪心”？
贪心算法的核心是：每一步都选择当前状态下最优的决策，最终得到全局最优解。
在跳跃游戏 II 中，这个“局部最优”就是：
在当前这一跳能到达的所有位置中，选择那个能让你下一步跳得最远的位置。
为什么这样能保证“最少跳跃次数”？
因为每一跳都在最大化你的覆盖范围，相当于在 BFS 的每一层中，你都在尽可能地扩张这一层的边界。当你扩展的边界第一次覆盖到终点时，你经历的层数就是最少的跳跃次数——这正好对应 BFS 在无权图中求最短路径。
直觉本质：这是一种“用尽每一跳的潜力”的策略。每一次跳跃就像在湖面扔一颗石子，我们要让这一波涟漪覆盖得尽可能远，这样需要的石子数（跳跃次数）才会最少。
3.2 机制层（How）：代码执行时的“时间切片”
defjump(nums):n=len(nums)jumps=0current_end=0# 当前这一跳能到达的最远边界farthest=0# 在 current_end 范围内，能到达的最远位置foriinrange(n-1):# 注意：不需要遍历最后一个位置farthest=max(farthest,i+nums[i])ifi==current_end:# 已经到达了当前跳的边界，必须再跳一次jumps+=1current_end=farthestifcurrent_end>=n-1:breakreturnjumps执行过程（以nums = [2, 3, 1, 1, 4]为例）：
初始: jumps = 0, current_end = 0, farthest = 0 i=0, nums[0]=2: farthest = max(0, 0+2) = 2 i == current_end (0 == 0) → 必须跳！ jumps = 1, current_end = 2 current_end >= 4? → 否 i=1, nums[1]=3: farthest = max(2, 1+3) = 4 i == current_end? (1 == 2) → 否，继续 i=2, nums[2]=1: farthest = max(4, 2+1) = 4 i == current_end? (2 == 2) → 必须跳！ jumps = 2, current_end = 4 current_end >= 4? → 是，结束 最终 jumps = 2关键洞察：
- 我们只在必须跳的时候才跳（
i == current_end），而不是在每个位置都尝试。 farthest记录了在当前跳的覆盖范围内，能到达的最远位置。这相当于 BFS 中“下一层的边界”。- 通过一次遍历，我们在 O(n) 时间内找到了最少跳跃次数。
3.3 本质层（What）：BFS 层级覆盖的数学逻辑
这道题本质上是一个无权图中的最短路径问题，但图的边是隐式的：
- 节点：数组的每个下标。
- 边：从节点
i可以跳到所有[i+1, i+nums[i]]内的节点。
为什么贪心就是 BFS？
- BFS 在无权图中求最短路径时，每一层都代表一次跳跃。
- 在 BFS 中，我们通常维护一个队列。但在这个隐式图中，我们不需要显式的队列——因为图是“连续”的，
current_end就是当前层的右边界，farthest就是下一层的右边界。
| BFS 概念 | 跳跃游戏 II 中的对应 |
|---|---|
| 队列 | 不需要，因为节点下标是连续的 |
| 当前层的最右节点 | current_end |
| 下一层的最右节点 | farthest |
| 层数（BFS 的 depth） | jumps |
| BFS 终止条件 | current_end >= n-1 |
本质提炼：贪心算法在这里实际上是 BFS 的一种高效实现——因为图的边具有“连续性”特征，我们可以用两个变量代替整个队列，将时间复杂度从 O(E) 降到 O(V)。
四、关键洞察（3个最重要的细节）
洞察 1：为什么遍历范围是range(n - 1)而不是range(n)？
如果遍历到最后一个位置（i = n-1），当i == current_end时，我们会增加一次不必要的跳跃。因为到达最后一个位置时，我们已经完成了任务，不需要再跳了。所以循环条件写成range(n - 1)可以避免这一冗余。
洞察 2：贪心的正确性证明
为什么“每步都选能到达最远位置的点”能保证全局最少跳跃次数？
直觉证明：
- 设第
k跳能到达的范围是[L, R]。在这一次跳跃中，我们选择了一个位置p ∈ [L, R]，它能让下一次跳跃到达最远的位置。 - 如果存在更优的方案，它必须在第
k跳时选择一个不同位置q，且q能到达比p更远的位置。但根据定义，p已经是能到达最远位置的点，所以q不可能超越p。 - 因此，贪心选择就是最优的。
这可以用“归纳法”严格证明——每一步的贪心选择都不会缩小未来的可能性。
洞察 3：与“跳跃游戏 I”的本质区别
| 特性 | 跳跃游戏 I（LeetCode 55） | 跳跃游戏 II（LeetCode 45） |
|---|---|---|
| 目标 | 判断能否到达终点 | 求最少跳跃次数 |
| 算法 | 维护最远可达距离 | 维护当前边界 + 下一层边界 |
| 返回值 | Boolean | 最小跳跃次数 |
| 贪心维度 | 存在性 | 最优化 |
跳跃游戏 I 只需要判断可行性，所以可以只维护farthest。而跳跃游戏 II 需要知道“当前跳到哪里了”，所以必须维护current_end——这是两者的核心区别。
五、代码实现（Python）
解法一：贪心 + BFS 层级覆盖（推荐）
defjump(nums):n=len(nums)jumps=0current_end=0farthest=0foriinrange(n-1):farthest=max(farthest,i+nums[i])ifi==current_end:jumps+=1current_end=farthestifcurrent_end>=n-1:breakreturnjumps解法二：DP 版本（O(n²)，不推荐，但可帮助理解）
defjump(nums):n=len(nums)dp=[float('inf')]*n dp[0]=0foriinrange(n):forjinrange(i+1,min(n,i+nums[i]+1)):dp[j]=min(dp[j],dp[i]+1)returndp[-1]六、图解示例
以nums = [2, 3, 1, 1, 4]为例：
位置: 0 1 2 3 4 跳跃能力: 2 3 1 1 4第一次跳跃：从0出发，覆盖[1, 2]
farthest = max(0+2, 1+3, 2+1) = 4- 边界
current_end扩大到4，说明这一跳就能到达终点。 - 实际上，我们跳到
1，然后1跳3步到4。
图解：
Step 0: 从 0 开始，能到 1 或 2 ┌─────────────────┐ │ [0] │ │ 跳1次(覆盖1~2) │ └────────┬────────┘ │ ┌────────┴────────┐ │ [1] [2]│ │ 跳3 跳1 │ └────────┬────────┘ │ ┌────────┴────────┐ │ [2],[3],[4] │ │ 到达终点！ │ └─────────────────┘七、复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 贪心 + BFS | O(n) | O(1) | 最优解 |
| DP | O(n²) | O(n) | 仅用于理解，不推荐 |
- 贪心解法只遍历了一次数组，且只用了 3 个变量。
- 空间复杂度 O(1) —— 这是这道题在面试中备受推崇的原因之一。
八、面试考点与注意事项
Q1：贪心算法与动态规划在这道题中的区别？
答：动态规划需要从后往前或从前往后计算每个位置的最少跳跃次数，时间复杂度 O(n²)。贪心算法通过维护“当前跳的边界”和“下一跳的最远距离”，在一次遍历中完成计算，时间复杂度 O(n)。贪心的有效性依赖于问题的最优子结构性质。
Q2：如果题目改成“跳跃游戏 I”（能否到达终点），代码如何修改？
答：只需要维护farthest，遍历每个位置时更新，如果某个i > farthest则返回 False。
defcanJump(nums):farthest=0foriinrange(len(nums)):ifi>farthest:returnFalsefarthest=max(farthest,i+nums[i])returnTrueQ3：为什么farthest要用max更新，而不是直接赋值？
答：因为farthest是“在当前 jump 覆盖范围内能到达的最远位置”，它应该综合所有可选项取最大值。直接赋值为i + nums[i]会丢失之前更优的选择。
九、知识图谱扩展：跳跃游戏与大模型搜索策略
在 AI 领域，尤其是大模型推理中，搜索策略是核心议题之一。
9.1 贪心与 Beam Search
| 跳跃游戏 II（贪心） | 大模型解码（Beam Search） |
|---|---|
| 每次选择能覆盖最远位置的下一个节点 | 每一步保留概率最高的 K 条候选路径 |
用farthest记录当前最优选择 | 用Beam Width控制搜索宽度 |
| 剪枝：只保留最优的下一跳 | 剪枝：丢弃低概率的候选词 |
| 本质：每一步都做“局部最优”决策 | 本质：每一步都做“概率上最优”的剪枝 |
两者的底层逻辑高度一致：在每一步，通过一个评分函数（距离 / 概率）对候选集合进行筛选，保留最有可能通往最优解的那部分。
9.2 从“最少跳跃”到“最少推理步骤”
在 LLM 推理中，我们也经常思考类似的问题：
如果我们要完成一个复杂的任务（如写一篇论文），最少需要多少次“推理步骤”才能达到目标？
这和“从起点跳到终点的最少步数”是同一类问题——每一步都是一个决策点，而你的能力（nums[i]）决定了你能覆盖哪些后续的决策点。大模型通过Chain-of-Thought（思维链）来扩展推理步骤，本质上是在探索一个“隐式图”，而贪心搜索和 Beam Search 都是这个图中的路径搜索策略。
十、三句话带走
- 直觉：就像接力赛，每一棒都要选一个“能让下一棒跑得最远”的接力点——这就是贪心的灵魂。
- 机制：用
current_end记录当前跳的边界，用farthest记录下一跳能到达的最远位置，每到达边界就跳一次。 - 本质：这是 BFS 在隐式图上的高效实现，用 O(1) 空间完成 O(n) 时间的层级扩张。
十一、留给你的思考题
问题：如果题目改成“最多跳跃次数”（而不是最少），你会如何修改代码？这种“最大化”版本在实际问题中对应什么场景？
提示：“最多跳跃次数”其实意味着你可以在每次跳跃时选择较小的步长，故意绕远路。这在现实中对应“故意消耗资源”或“延迟满足”的场景。算法上，这个问题就变成了“能否在每一步都合法地耗尽可能多的步数”——这可能比“最少”更容易解决。
连接到大模型：在大模型生成中，我们有时需要控制输出的长度（如摘要任务要求字数限制）。如果我们希望生成更长的回答，可以在每一步选择较短的跳转（即生成更保守的 token），这与“最大化跳跃次数”有异曲同工之妙。
思考一下：如果 LLM 的“推理步数”可以像跳跃游戏一样被量化，那么“最少步数”和“最可靠步数”之间如何权衡？🤔