【学习记录】跳跃游戏 II从“接力赛”到“BFS 层级覆盖”——贪心 BFS 的经典范式在学习了“两数之和”中用哈希表记录历史状态的思维之后我们来到了另一个完全不同的领地——贪心算法与 BFS广度优先搜索。如果说两数之和是“用空间换时间”的典范那么跳跃游戏 IILeetCode 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):nlen(nums)jumps0current_end0# 当前这一跳能到达的最远边界farthest0# 在 current_end 范围内能到达的最远位置foriinrange(n-1):# 注意不需要遍历最后一个位置farthestmax(farthest,inums[i])ificurrent_end:# 已经到达了当前跳的边界必须再跳一次jumps1current_endfarthestifcurrent_endn-1:breakreturnjumps执行过程以nums [2, 3, 1, 1, 4]为例初始: jumps 0, current_end 0, farthest 0 i0, nums[0]2: farthest max(0, 02) 2 i current_end (0 0) → 必须跳 jumps 1, current_end 2 current_end 4? → 否 i1, nums[1]3: farthest max(2, 13) 4 i current_end? (1 2) → 否继续 i2, nums[2]1: farthest max(4, 21) 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 本质层WhatBFS 层级覆盖的数学逻辑这道题本质上是一个无权图中的最短路径问题但图的边是隐式的节点数组的每个下标。边从节点i可以跳到所有[i1, inums[i]]内的节点。为什么贪心就是 BFSBFS 在无权图中求最短路径时每一层都代表一次跳跃。在 BFS 中我们通常维护一个队列。但在这个隐式图中我们不需要显式的队列——因为图是“连续”的current_end就是当前层的右边界farthest就是下一层的右边界。BFS 概念跳跃游戏 II 中的对应队列不需要因为节点下标是连续的当前层的最右节点current_end下一层的最右节点farthest层数BFS 的 depthjumpsBFS 终止条件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”的本质区别特性跳跃游戏 ILeetCode 55跳跃游戏 IILeetCode 45目标判断能否到达终点求最少跳跃次数算法维护最远可达距离维护当前边界 下一层边界返回值Boolean最小跳跃次数贪心维度存在性最优化跳跃游戏 I 只需要判断可行性所以可以只维护farthest。而跳跃游戏 II 需要知道“当前跳到哪里了”所以必须维护current_end——这是两者的核心区别。五、代码实现Python解法一贪心 BFS 层级覆盖推荐defjump(nums):nlen(nums)jumps0current_end0farthest0foriinrange(n-1):farthestmax(farthest,inums[i])ificurrent_end:jumps1current_endfarthestifcurrent_endn-1:breakreturnjumps解法二DP 版本O(n²)不推荐但可帮助理解defjump(nums):nlen(nums)dp[float(inf)]*n dp[0]0foriinrange(n):forjinrange(i1,min(n,inums[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(02, 13, 21) 4边界current_end扩大到4说明这一跳就能到达终点。实际上我们跳到1然后1跳3步到4。图解Step 0: 从 0 开始能到 1 或 2 ┌─────────────────┐ │ [0] │ │ 跳1次(覆盖1~2) │ └────────┬────────┘ │ ┌────────┴────────┐ │ [1] [2]│ │ 跳3 跳1 │ └────────┬────────┘ │ ┌────────┴────────┐ │ [2],[3],[4] │ │ 到达终点 │ └─────────────────┘七、复杂度分析解法时间复杂度空间复杂度说明贪心 BFSO(n)O(1)最优解DPO(n²)O(n)仅用于理解不推荐贪心解法只遍历了一次数组且只用了 3 个变量。空间复杂度 O(1) —— 这是这道题在面试中备受推崇的原因之一。八、面试考点与注意事项Q1贪心算法与动态规划在这道题中的区别答动态规划需要从后往前或从前往后计算每个位置的最少跳跃次数时间复杂度 O(n²)。贪心算法通过维护“当前跳的边界”和“下一跳的最远距离”在一次遍历中完成计算时间复杂度 O(n)。贪心的有效性依赖于问题的最优子结构性质。Q2如果题目改成“跳跃游戏 I”能否到达终点代码如何修改答只需要维护farthest遍历每个位置时更新如果某个i farthest则返回 False。defcanJump(nums):farthest0foriinrange(len(nums)):ififarthest:returnFalsefarthestmax(farthest,inums[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 的“推理步数”可以像跳跃游戏一样被量化那么“最少步数”和“最可靠步数”之间如何权衡