教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文基于「算法通关手册」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$ 前面的点到达的。所以我们可以通过贪心算法来计算出所能到达的最远位置。具体步骤如下初始化能到达的最远位置 $max_i$ 为 $0$。遍历数组nums。如果能到达当前位置即 $max_i \ge i$并且当前位置 当前位置最大跳跃长度 能到达的最远位置即 $i nums[i] max_i$则更新能到达的最远位置 $max_i$。遍历完数组最后比较能到达的最远位置 $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 - 17. 复杂度分析时间复杂度$O(n)$其中 $n$ 是数组nums的长度。空间复杂度$O(n)$使用一维dp数组保存状态。8. 两种思路的对比对比维度思路 1贪心思路 2动态规划核心维护量单个变量max_i当前最远可达一维数组dp[i]前缀最远可达状态是否保留不保留滚动更新完整保留每一步状态时间复杂度$O(n)$$O(n)$空间复杂度$O(1)$$O(n)$工程侧重点代码最简、面试首选便于理解可达能力的传递过程两种思路的时间复杂度相同但贪心将空间压缩到 $O(1)$且代码更简洁因此工程与面试场景下通常优先选择贪心写法。源码级验证与算法家族拓展在仓库中的知识定位「跳跃游戏」是仓库算法知识体系中「贪心算法」章节的典型应用例题可结合 07_05_greedy_algorithm.md 复习贪心思想的适用条件同时它在「分类刷题清单」中与 数组 / 双指针 / 滑动窗口 等专题相邻适合按专题集中训练。系列题横向对照仓库内可继续深挖同一个「跳跃」主题在仓库中还有多道姊妹题对比它们的差异可以加深对本题解法的理解题目题解位置玩法差异推荐解法0045. 跳跃游戏 II中等求「到达最后下标的最小跳跃次数」保证可达贪心边界endmax_pos$O(n)$动态规划朴素版 $O(n^2)$ 会超时1306. 跳跃游戏 III中等从start出发每次可向左或向右跳arr[i]步判断能否到达值为 0 的下标BFS 层序遍历$O(n)$1345. 跳跃游戏 IV困难从下标 0 出发可跳到i±1或任意同值下标求到达末尾的最少步数BFS 同值分组剪枝$O(n)$可以看出本题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 题清单 规划系统训练。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐跳跃游戏LeetCode 55. Jump Game贪心算法全解可达性判断与多语言实现跳跃游戏LeetCode 55. Jump Game贪心算法全解可达性判断与多语言实现 本篇技术指南以 leetcode 题解仓库中的 problems/文档教程知识库AlgoNote「算法通关手册」LeetCode 0072 编辑距离Levenshtein Distance双串动态规划全解AlgoNote「算法通关手册」LeetCode 0072 编辑距离Levenshtein Distance双串动态规划全解 本篇题解基于开源仓库 Alg教程文档知识库VLC视频转码终极指南如何免费将任何视频转换为理想格式VLC视频转码终极指南如何免费将任何视频转换为理想格式 VLC媒体播放器不仅是全球最受欢迎的多媒体播放器更是一个功能强大的视频转码工具。这款开源软件能让你免教程文档知识库上一篇ChirpStack Network Server与Gateway Bridge无缝集成教程实现网关数据高效传输下一篇开发者必看RWD-Table-Patterns的响应式实现原理与核心代码解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考