企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本文基于「算法通关手册」AlgoNote 仓库中的 0055. 跳跃游戏 题解文档，系统讲解 LeetCode 经典中等题「跳跃游戏」（Jump Game）的两种解法：贪心算法与动态规划。文章不仅完整复刻原文档的题面、推导过程与可运行代码，还结合仓库的算法知识体系（贪心算法讲解）与「跳跃游戏」系列题（跳跃游戏 II、跳跃游戏 III、跳跃游戏 IV）做横向对比。读完本文，你将掌握「最远可达位置」这一贪心模型的推导逻辑、两种解法的状态定义与复杂度差异，并能顺藤摸瓜刷完整个跳跃游戏系列。

题目链接与基本信息

• 题目：0055. 跳跃游戏 - 力扣
• 标签：贪心、数组、动态规划
• 难度：中等
• 题解所在仓库位置：docs/solutions/0001-0099/jump-game.md

该题在「算法通关手册」的题解体系中被归入 0001-0099 题解目录，同时是「面试 200 题刷题清单」与「分类刷题清单」中「贪心 / 数组」分类下的必刷题目之一，属于面试高频考点。

题目大意与约束

描述：给定一个非负整数数组nums，数组中每个元素代表在该位置可以跳跃的最大长度。开始位置位于数组的第一个下标处。

要求：判断是否能够到达最后一个下标。

说明（数据范围）：

• $1 \le nums.length \le 3 \times 10^4$。
• $0 \le nums[i] \le 10^5$。

示例：

• 示例 1：

输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

• 示例 2：

输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

题眼：数组中每个元素是「在该位置可以跳跃的最大长度」，而不是固定步长——这意味着只要某一段区间内任意一点可达，该点能覆盖到的所有位置就全部可达，这正是贪心算法成立的根本前提。同时，$n \le 3 \times 10^4$ 的数据规模决定了我们需要 $O(n)$ 级别的解法（$O(n^2)$ 会超时），这也为动态规划思路的设计划定了优化方向。

解题思路

思路 1：贪心算法（推荐）

1. 核心思想

如果我们能通过前面的某个位置 $j$，到达后面的某个位置 $i$，则我们一定能到达区间 $[j, i]$ 中所有的点（$j \le i$）。

而前面的位置 $j$ 肯定也是通过 $j$ 前面的点到达的。所以我们可以通过贪心算法来计算出所能到达的最远位置。具体步骤如下：

1. 初始化能到达的最远位置 $max_i$ 为 $0$。
2. 遍历数组nums。
3. 如果能到达当前位置，即 $max_i \ge i$，并且当前位置 + 当前位置最大跳跃长度 > 能到达的最远位置，即 $i + nums[i] > max_i$，则更新能到达的最远位置 $max_i$。
4. 遍历完数组，最后比较能到达的最远位置 $max_i$ 和数组最远距离 $size - 1$ 的关系。如果 $max_i \ge size - 1$，则返回True，否则返回False。

2. 贪心正确性说明

这一步只维护一个变量「当前能到达的最远下标」，并始终选取所有可达点中「跳得最远」的那个来扩张边界，因此每一步都是局部最优；而由于跳跃能力具有「可达区间连续」的性质，局部最优的不断累积恰好构成全局最优解——这是贪心算法能在此题成立的本质原因，与仓库中 07_05_greedy_algorithm.md 阐述的贪心算法「每一步局部最优 + 无后效性」理论框架完全对应。

3. 代码

class Solution: def canJump(self, nums: List[int]) -> bool: size = len(nums) max_i = 0 for i in range(size): if max_i >= i: max_i = max(max_i, i + nums[i]) return max_i >= size - 1

代码解读：

• max_i >= i是「当前位置可达」的判定：只要当前位置仍在已探测到的最远范围内，就可以从该点起跳；
• max_i = max(max_i, i + nums[i])以取最大值的方式不断扩张可达边界；
• 循环结束后只需判断max_i >= size - 1，即最远可达下标是否覆盖到数组最后一个下标。

4. 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组nums的长度（单次线性扫描）。
• 空间复杂度：$O(1)$（仅使用常数个辅助变量）。

思路 2：动态规划

除贪心外，本题也可以从动态规划的视角建模，理解这一视角对后续刷「跳跃游戏 II」等系列题大有裨益。

1. 阶段划分

按照位置进行阶段划分，即从左到右依次处理下标 $0, 1, \dots, size-1$。

2. 定义状态

定义状态 $dp[i]$ 表示为：从位置 $0$ 出发，经过 $j \le i$，可以跳出的最远距离。

注意该状态与直觉上的「能否到达 i」不同，它记录的是「到达 i 时已经掌握的最远跳达能力」，这使得转移只需依赖前一个位置的状态。

3. 状态转移方程

• 如果能通过 $0 \sim i - 1$ 个位置到达 $i$，即 $dp[i-1] \ge i$，则 $dp[i] = max(dp[i-1],\ i + nums[i])$；
• 如果不能通过 $0 \sim i - 1$ 个位置到达 $i$，即 $dp[i - 1] < i$，则 $dp[i] = dp[i - 1]$（能力不再增长）。

4. 初始条件

初始状态下，从 $0$ 出发，经过 $0$，可以跳出的最远距离为 $nums[0]$，即 $dp[0] = nums[0]$。

5. 最终结果

根据我们之前定义的状态，$dp[i]$ 表示：从位置 $0$ 出发，经过 $j \le i$，可以跳出的最远距离。因此需要判断 $dp[size - 1]$ 与数组最远距离 $size - 1$ 的关系：若 $dp[size - 1] \ge size - 1$ 则可到达最后一个下标。

6. 代码

class Solution: def canJump(self, nums: List[int]) -> bool: size = len(nums) dp = [0 for _ in range(size)] dp[0] = nums[0] for i in range(1, size): if i <= dp[i - 1]: dp[i] = max(dp[i - 1], i + nums[i]) else: dp[i] = dp[i - 1] return dp[size - 1] >= size - 1

7. 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组nums的长度。
• 空间复杂度：$O(n)$（使用一维dp数组保存状态）。

8. 两种思路的对比

两种思路的时间复杂度相同，但贪心将空间压缩到 $O(1)$，且代码更简洁，因此工程与面试场景下通常优先选择贪心写法。

源码级验证与算法家族拓展

在仓库中的知识定位

「跳跃游戏」是仓库算法知识体系中「贪心算法」章节的典型应用例题，可结合 07_05_greedy_algorithm.md 复习贪心思想的适用条件；同时它在「分类刷题清单」中与 数组 / 双指针 / 滑动窗口 等专题相邻，适合按专题集中训练。

系列题横向对照（仓库内可继续深挖）

同一个「跳跃」主题在仓库中还有多道姊妹题，对比它们的差异可以加深对本题解法的理解：

可以看出：本题（0055）的贪心解法是「区间扩张型」贪心的入门模板，而跳跃游戏 II 将其升级为「步数计数」；跳跃游戏 III / IV 则跳出了「只能向右跳」的框架，演化为图上的 BFS 最短路问题。将四题串联起来刷，可以完整覆盖「可达性判定 → 最少步数 → 双向可达 → 同值可达」这一递进脉络。

总结

• 核心结论：LeetCode 0055 跳跃游戏可以用「贪心」与「动态规划」两种 $O(n)$ 算法求解；贪心以 $O(1)$ 空间和更简洁的代码成为最优解，动态规划则帮助理解状态转移的来龙去脉。
• 背诵要点：贪心一行式max_i = max(max_i, i + nums[i])配合可达判定max_i >= i，即可完成可达性判断。
• 刷题路线：掌握本题后，建议按 跳跃游戏 II → 跳跃游戏 III → 跳跃游戏 IV 的顺序进阶，并结合 贪心算法章节 与 面试 200 题清单 规划系统训练。

• 教程
• 文档
• 知识库