我一直觉得“跳跃游戏”这个题系列是算法面试里性价比极高的一类题目。它不像红黑树那样需要很强的记忆也不像线段树那样上来就是大模板它更像是一组“智力体操”从最简单的贪心到动态规划再到图论BFS同一张“跳跃”的外壳底下藏的是好几种完全不同的算法思想。这个系列在LeetCode上从55题一直排到1345题横跨了贪心、DP、DFS、BFS、滑动窗口等考点。很多准备面试的朋友会把它们当成“题海”来做做完就忘换个马甲就不认识了。我这篇文章的定位很明确把这组题当作一个整体来拆讲清楚每一道题的设计逻辑、解法选型、以及背后的思维模型。无论你是刚开始刷题的新手还是准备冲刺一线大厂、想把套路内化的人这篇都能给你一个相对完整的地图。1. 跳跃游戏题集到底在考什么1.1 从一道题长出的一个家族很多人第一次接触跳跃游戏是从LeetCode 55题开始的。题目描述很直观给你一个非负整数数组每个元素代表你在该位置可以跳跃的最大长度从下标0出发判断能不能跳到最后一个下标。就是这道看似简单、初期被标记为“贪心”的题目往后延伸出了一整个家族。LeetCode 45题把“能不能”升级成了“最少几步能到”LeetCode 1306题换了一个起点让你从某个下标出发左右跳跃看能否碰到值为0的位置LeetCode 1345题干脆把数组变成了一个无向图你不仅可以按索引跳还能瞬移到所有相同值的位置问最短几步到达终点更夸张的是LeetCode 1340题把跳跃变成带高度差的“爬山”必须严格往低处跳问最多能访问多少个点。你别看这些题目都叫“跳跃游戏”它们的解法完全不同。有人认为“跳跃游戏”就是贪心这其实是幸存者偏差因为最热门的55题和45题是贪心但后面的题目早就上升到动态规划和图论层面了。我甚至见过有人在听别人讲1345题时一脸懵说“这不是跳跃游戏怎么用BFS了”这说明他把“跳跃游戏”狭义地理解成了一道题而不是一个题家族。1.2 这类题型的题眼在哪里我自己刷完这一整个系列后最大的感受是跳跃游戏系列的核心题眼不是“跳跃”而是“覆盖范围”和“状态转移”。你站在当前格子如果你能跳的最远距离是k那么你其实可以覆盖当前格子到当前格子k之间的所有格子。这个“覆盖区间”是后面所有解法的基础。所以当你遇到跳跃类的题目时第一反应不应该是套模板而是问自己三个问题题目问的是“可行性”还是“最优解”可行性问题比如55题往往可以用贪心思想解决因为只需要判断区间能否覆盖终点最优解问题比如45题可能需要贪心、DP或BFS需要进一步判断。跳跃的方式是单向还是双向单向跳跃天然适合从头到尾线性推导双向跳跃则明显带有图论特征大概率要转化为BFS求最短路。决策是否具有“无后效性”如果你知道站在某个位置时的最佳结果并且不会因为后面的选择而改变前面的结果那么DP是合适的如果局部最优推导全局最优成立那么贪心更简洁。这三个问题几乎能帮你在5秒内定位一道跳跃类题目的解法方向。接下来我按题目维度拆解每一道题都会从思路、实现细节、复杂度三个维度深入。2. 五大核心题目的设计与解法拆解2.1 跳跃游戏LeetCode 55贪心的经典教学LeetCode 55题我刷过很多次每次给初学者讲我都坚持先让他们自己想几分钟不要急着看题解。大部分人会想到递归回溯从0开始枚举每个能跳到的位置看能不能到达终点。这样当然能做对但时间复杂度是指数级的在大数组下必然超时。正确的解法可以用一个非常优美的贪心思路维护一个当前能到达的最远位置maxReach遍历数组的过程中不断更新maxReach。如果遍历过程中某个位置i已经在maxReach之外即i大于maxReach说明你根本走不到这个位置直接返回false。如果maxReach已经大于等于最后一个下标直接返回true。def canJump(nums): max_reach 0 n len(nums) for i in range(n): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach n - 1: return True return True这个解法之所以成立是因为它利用了一个关键性质如果i位置可达那么所有小于i的位置都可达因为maxReach是从前往后不断累加的区间覆盖。所以只要有某个位置超过了maxReach那么从0到i-1之间的所有位置都无法越过这个“断点”。这个题我建议你彻底吃透因为它衍生出的一个变体是如果数组中有些元素为0中间可能会断裂怎么办其实上面的贪心解法天然地处理了这种情况——只要有位置i maxReach就说明中间出现了无法跳过的“0”会立即返回false。你可以用这个例子手动模拟一下[3,2,1,0,4]当遍历到i3时maxReach3i maxReach不越界但nums[3] 0所以maxReach还是3i4时4 3返回false完美。2.2 跳跃游戏 IILeetCode 45贪心步数与DP的纠葛这道题是55题的进阶版假设你一定可以到达终点问你最少需要跳几次。很多55题做得很熟的人到了45题会惯性套用“记录最远距离”的思路结果发现并不会得到最少步数因为“当前跳得最远”不等于“整体步数最少”。先看贪心解法准确说这是“贪心思想 区间扫描”的解法。它维护两个变量当前这一步能到达的右边界curEnd以及下一步能到达的最远位置nextEnd。遍历数组时不断更新nextEnd max(nextEnd, i nums[i])。当i到达curEnd时说明这一跳的极限到了必须增加一步step然后把curEnd更新为nextEnd。不停重复直到curEnd覆盖终点。def jump(nums): n len(nums) if n 1: return 0 steps 0 cur_end 0 next_end 0 for i in range(n - 1): # 最后一格不用跳 next_end max(next_end, i nums[i]) if i cur_end: steps 1 cur_end next_end if cur_end n - 1: return steps return steps这个解法的精妙之处在于它把跳跃过程看成了一段一段的“扩张区间”每一跳只关心上一步的覆盖面内能延伸到多远。它并不是真的“在当前步选择跳多远”而是在当前步能覆盖的区间内评估下一步能到哪儿然后果断迈出去。这里还有一道分岔路45题也可以用动态规划做转移方程是dp[i] min(dp[i], dp[j] 1)其中j是能跳到i的前驱位置。但这样做的时间复杂度是O(n^2)在大数据量下非常吃亏。所以我建议你优先掌握贪心解法并且要能说清楚它是如何把O(n^2)优化到O(n)的。面试时你能主动说出两种解法的复杂度对比会显得理解更全面。2.3 跳跃游戏 IIILeetCode 1306从跳跃变成图遍历LeetCode 1306题看起来仍然是个跳跃题给你一个数组arr和一个起始下标start你在每个位置i可以跳到iarr[i]或i-arr[i]问能否跳到某个值为0的位置。但稍微分析就会发现这已经不是一个“线性的覆盖问题”了而是一个“图的可达性问题”每个下标是一个节点每个位置有最多两条有向边向左、向右。这个题的通用解法是DFS或BFS。我从实际经验出发推荐BFS原因是BFS天然避免递归深度过大的问题而且在“能否到达”这类问题里BFS与DFS的时间复杂度相当但BFS的实现更容易通过迭代完成不容易踩爆栈。from collections import deque def canReach(arr, start): n len(arr) visited [False] * n queue deque([start]) visited[start] True while queue: i queue.popleft() if arr[i] 0: return True for nxt in (i arr[i], i - arr[i]): if 0 nxt n and not visited[nxt]: visited[nxt] True queue.append(nxt) return False这里有一个细节值得注意访问标记必须入队时就置为True而不是出队时。如果出队时才标记那同一个节点可能被多次加入队列虽然不会死循环但会浪费大量时间严重时导致不必要的重复遍历。这个坑我在给同事review代码时见过很多次。判断这个题能不能用可达性模型有一个很直观的信号只要题目允许你“双向走”并且问的是“能否到达某个目标”那么八成是图论问题。你可以把数组想象成一堆并排的房子每个房子的门只通向固定的另一个房子你要判断从某间房子出发能不能走到一间特定的房子。这不就是迷宫吗迷宫就是图。2.4 跳跃游戏 IVLeetCode 1345最短路BFS和编码技巧LeetCode 1345题是跳跃游戏系列里少有的“图论味道”更浓的题。题目给你一个整数数组arr你站在下标0目标是跳到n-1。你每次可以往左或右移动一步也可以跳到任意一个与当前值相同的下标上求最少步数。我第一次做的时候第一反应是直接BFS邻接表思维每个下标是一个节点左右各一个邻居再加上所有值相同的下标。但是如果你真的为每个节点去遍历所有相同值的下标在最坏情况下会退化到O(n^2)比如数组里所有值都相同。正确的优化手段是把相同值的索引分组成一个“桶”。BFS过程中当第一次遇到某个值时把这个值对应的所有索引一次性加到队列里然后立即清空这个值的桶。为什么要清空因为BFS是按层遍历的第一次到达某个值时所有同值节点的距离就都确定了后续再遇到这个值只会白白增加重复计算。from collections import defaultdict, deque def minJumps(arr): n len(arr) if n 1: return 0 value_to_indices defaultdict(list) for i, v in enumerate(arr): value_to_indices[v].append(i) queue deque([0]) visited set([0]) steps 0 while queue: for _ in range(len(queue)): i queue.popleft() if i n - 1: return steps for nxt in (i - 1, i 1): if 0 nxt n and nxt not in visited: visited.add(nxt) queue.append(nxt) if arr[i] in value_to_indices: for j in value_to_indices[arr[i]]: if j not in visited: visited.add(j) queue.append(j) del value_to_indices[arr[i]] steps 1 return -1注意代码里我在遍历同值节点后立即del掉这个桶这是一个关键操作。如果不清空那些已经被访问过的同值节点会在后面的层中被疯狂重复入队时间开销会非常大。这个题的编码细节比45题复杂得多我建议你训练自己手写BFS的骨架队列、visited、steps分层。熟练之后这套骨架几乎可以通吃所有最短步数问题。2.5 跳跃游戏 VLeetCode 1340与跳跃游戏 VILeetCode 1696DP的花式变形到了1340题跳跃系列从图论又转向了记忆化搜索和动态规划。题目要求你从任意位置出发最多跳d步且只能跳到严格低于当前高度的地方问最多能访问多少个下标。这个题的暴力做法是DFS枚举所有路径但是高度限制造成了大量重叠子问题所以必须用记忆化。dp[i]表示从i出发最多能访问的节点数。转移时枚举所有能跳到的位置j取max(dp[j])1。为了保证“只能往低处跳”这个约束可计算很多实现会先按高度排序但更自然的写法是递归 记忆化。from functools import lru_cache def maxJumps(arr, d): n len(arr) lru_cache(None) def dfs(i): res 1 j i - 1 while j 0 and i - j d and arr[j] arr[i]: res max(res, dfs(j) 1) j - 1 j i 1 while j n and j - i d and arr[j] arr[i]: res max(res, dfs(j) 1) j 1 return res return max(dfs(i) for i in range(n))这个递归的终止条件其实是隐含的当左右都被更高的墙挡住或者超出步数限制时两个while循环都不会执行dfs返回1。这就是“当前节点本身”这个基础情况。LeetCode 1696题则是另一个方向的变形每次可以跳1到k步求到终点的最大得分。这个题的朴素DP是O(nk)但可以用单调队列优化到O(n)。关于这道题我的建议是先搞懂朴素DP再看单调队列优化。跳过朴素DP直接看优化很容易被滑动窗口里的单调性绕晕。3. 实战套路遇到跳跃类题目怎么快速定位解法3.1 判断“可行性”和“最优解”是第一优先级我刷题有个习惯拿到题目先看它问什么。问“能不能到达”是可行性问题通常适合用贪心、DFS、BFS问“最少几次”“最多几个”是最优化问题通常适合用DP、BFS最短路、带优化的贪心。为什么这个判断很重要因为它直接决定了你的代码结构。如果是可行性问题你通常只需要一个状态值比如“当前可达的最远距离”不需要为每个位置保存多个候选结果如果是最优化问题你几乎必然需要维护一个数组或队列来保存中间计算值。我举一个很典型的场景LeetCode 55题和45题用的是同一个数组但一个问“能不能”一个问“最少几次”。你只要把问题的性质判断错了很容易写出一个“判断可达但在某些用例下步数不是最少”的错误代码。3.2 用“单双向”判断是否要转图论这是跳跃系列最容易忽略的一条经验。如果题目里只能从当前位置向一个方向跳比如只能向后跳那大概率是一个线性DP或贪心题如果允许同时向左和向右跳或者允许跳转到相同值那么问题性质已经发生了根本变化必须用图论模型。我对图论模型的识别标准很简单“状态之间的转移是否有环”。只要转移有环就不能用线性DP或单纯贪心因为你的状态可能无限循环。比如LeetCode 1306题你从位置i跳到j后面可能又从j跳回i如果你用DP直接递推会遇到循环依赖。这时候BFS/DFS就是更自然的选择。3.3 边界条件自查清单在跳跃游戏系列里我踩过不少边界条件的坑总结成以下自查清单数组长度为1时是否特判很多题在n1时应该返回0或true不特判容易越界。最远跳跃距离是否为0如果所有格子都是0那么除了起点之外任何格子都不可达。步数限制是否包含“刚好跳到”和“超过终点”有些题目要求严格小于有些允许等于需要仔细读题。双向跳跃时是否检查index的范围这是1306题最常见的bug来源越界访问会直接报错。同值跳转时visited标记是否覆盖了所有同值节点漏掉任何一个都会导致死循环。这些边界条件看似琐碎但它们是面试官最喜欢的追问点。把边界条件逐一讲清楚比单纯把代码写对更能体现你的思维严密性。4. 面试和刷题中的错误、心得与提升路径4.1 我在这个系列上踩过的坑第一次做55题的时候我用的是DFSvisited的思路结果在一个很长的用例上超时了。后来才意识到这个题根本不需要维护路径访问因为“能否到达”只需要维护可达区间。这也是我后来反复强调“先判断题眼”的原因如果一开始就能识别出“覆盖区间”而不是“路径搜索”55题就是一道一行核心逻辑的题。45题是最容易写出“看起来对但步数不对”的题。常见错误是在每次更新nextEnd之后都立即steps导致多计步数。这个问题的本质是没能区分“当前步的节点”和“下一步的覆盖范围”建议大家在草稿纸上手动模拟一次[2,3,1,1,4]的过程把每一步的curEnd和nextEnd写下来很多疑惑都会消失。1345题我踩过一个很狡猾的坑把同值节点直接全部加入队列但没有立即删除桶导致队列中大量重复元素。那是极端的坏例子——数组长度超过10000所有元素相同结果队列膨胀得异常严重跑了好久才出结果。所以我在上文的代码里特意写了del value_to_indices[arr[i]]。这个设计不是锦上添花而是性能的必需。4.2 如何高效训练这组题我把跳跃游戏系列的训练路径分为三个阶段第一阶段是“一题多解”。挑55题和45题分别用贪心、DP、DFS、BFS写一遍虽然有些方法会超时但能加深理解重点体会不同算法的局限性和适用场景。比如用DFS做55题你会理解为什么“路径搜索”在这个题里是多余的用DP做45题你会明白为什么O(n^2)对于大数据量不可行。第二阶段是“同类对比”。把55、45、1306、1345、1340、1696这六道题放在一起做每做完一道写下它和其他题的区别。我自己的总结如下题目问题类型核心算法时间复杂度55 跳跃游戏可行性贪心O(n)45 跳跃游戏 II最优解贪心/DPO(n)/O(n^2)1306 跳跃游戏 III可行性BFS/DFSO(n)1345 跳跃游戏 IV最优解BFS 哈希分组O(n)1340 跳跃游戏 V最优解DP 记忆化O(n*d)1696 跳跃游戏 VI最优解DP 单调队列O(n)第三阶段是“自己出变体”。把你对题目的理解转化成新的题目比如把55题改成“最多只能跳k次能否到达终点”或者把1345题改成“求路径中经过的最小值之和”。这种自编题目的过程能让你发现原题的条件限制到底卡在哪里以及哪些算法性质才是真正不可绕过的。4.3 面试现场的表现建议面试遇到跳跃游戏系列我的建议是不要直接写代码。先花30秒到1分钟做三件事复述题目并确认输入输出规则说明你判断出的问题类型可行/最优说出你要用的算法及复杂度。这三点做完面试官基本已经对你的思路有信心了。写代码时尽量做到“变量名表意清晰”。一个叫maxReach的变量比一个叫tmp的变量更能让面试官看到你的逻辑。而且在while或for循环里主动加上注释说明“当前区间覆盖到的位置”和“下一步能覆盖的最远位置”分别是什么这种注释在45题里尤其加分。如果面试官问“能不能优化”不要只说“可以”。直接把思路说清楚如果是DP说明使用什么数据结构优化如果是BFS说明用什么方式避免重复访问。跳跃游戏系列的优化点各不相同但核心都是“减少无效遍历”。最后分享一个我从这组题里悟到的通用经验算法题不是背出来的是“用逻辑推”出来的。每个题看起来千变万化但只要你先把“可行性/最优解”判断清楚再把“单双向/环”判断清楚解法方向基本就锁定了。剩下的工作就是在选定的算法框架里把实现细节做干净。这组跳跃游戏是我见过的最好的算法思维训练场之一。
