跳跃游戏系列：贪心与DP的边界判断与选择
跳跃游戏系列：贪心与DP的边界判断与选择
适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约20分钟 | 难度：Medium
开篇故事
跳跃游戏这道题，我在面试阿里的时候遇到过类似的变种。面试官给了个场景：一个游戏关卡由一系列房间组成，每个房间有一把钥匙能开未来最多 k 个门，问能不能从第一个房间到达最后一个。
我当时秒出了贪心解——维护"目前能到达的最远位置"，如果当前位置超出了最远位置就说明走不到了。面试官表示满意，然后追问：如果要问"最少跳几步"呢？
这就是 LeetCode 45 跳跃游戏 II 的问题。我花了大概五分钟理清了思路：维护当前层的边界（BFS 思维），在当前层内找下一层的最远位置，跳出当前层边界时步数加一。
55 和 45 是一对非常互补的题目：55 问"能不能到"，45 问"最少几步到"。55 用贪心一次遍历，45 稍复杂但也是贪心，不需要 DP。很多人下意识用 DP 做这两道题，反而做复杂了。
一、题目解析
LeetCode 55. 跳跃游戏
给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。
输入：nums = [2,3,1,1,4]
输出：true
解释：从下标 0 跳 1 步到下标 1，再从下标 1 跳 3 步到最后一个下标
输入：nums = [3,2,1,0,4]
输出：false
解释：无论如何，总会到达下标 3，但该下标的最大跳跃长度是 0，所以永远不能到达最后一个下标LeetCode 45. 跳跃游戏 II
同样的规则，但要求返回到达最后一个下标的最少跳跃次数（保证一定可以到达）。
输入：nums = [2,3,1,1,4]
输出：2
解释：跳到下标 1，再跳到最后一个下标（最少 2 步）
输入：nums = [2,3,0,1,4]
输出：2考察的核心知识点：
- 贪心：局部最优（每步都到最远）能否推出全局最优
- DP：能否用 DP 解，和贪心比较哪个更优
- BFS 思维：把每步跳跃看作 BFS 的一层
二、LeetCode 55 解法：贪心一次遍历
解法一：DP（O(n²)，较慢）
dp[i] = 下标 i 是否可达。dp[0] = true，dp[i] = true 如果存在 j < i 使得 dp[j] == true && j + nums[j] >= i。
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && j + nums[j] >= i) {
dp[i] = true;
break;
}
}
}
return dp[n - 1];
}
}时间复杂度：O(n²)，空间复杂度：O(n)。
解法二：贪心（O(n)，最优）
维护 maxReach：目前能到达的最远位置。遍历每个位置，如果当前位置 > maxReach，说明到不了这里，直接返回 false。否则更新 maxReach = max(maxReach, i + nums[i])。
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
// 当前位置超出了能到达的最远范围，走不到这里
if (i > maxReach) return false;
// 更新能到达的最远位置
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}
}时间复杂度：O(n)，空间复杂度：O(1)。
我在 LeetCode 提交，运行时间 1ms，击败 99.9% 的 Java 用户。
贪心的正确性证明： 如果位置 i 可达（i <= maxReach），那么所有 i 到 i+nums[i] 的位置都可达，maxReach 取的是全局最大可达位置。如果某个位置 j 不可达（j > maxReach），那么 j 后面的所有位置也不可达（无法越过这个断点）。
三、LeetCode 45 解法：BFS 层次遍历思维
解法一：DP（O(n²)）
dp[i] = 到达下标 i 的最少跳跃次数。dp[0] = 0，对每个 j，dp[i] = min(dp[j] + 1) 对所有可以从 j 跳到 i 的 j。
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] != Integer.MAX_VALUE && j + nums[j] >= i) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
}时间复杂度：O(n²)，空间复杂度：O(n)。
解法二：贪心+BFS 层次（O(n)，最优）
把每次跳跃当作 BFS 的一层。维护：
curEnd：当前层能到达的最远位置（当前轮跳跃结束的边界）farthest：下一层能到达的最远位置（下一轮跳跃的最远边界）jumps：跳跃次数（层数）
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int jumps = 0;
int curEnd = 0; // 当前这一跳能覆盖的最远位置
int farthest = 0; // 在当前这一跳的范围内，下一跳最远能到哪
// 注意：不需要遍历最后一个元素（i < n-1），因为到达最后一个元素就算了
for (int i = 0; i < n - 1; i++) {
// 更新下一步能到达的最远位置
farthest = Math.max(farthest, i + nums[i]);
// 到达当前层的边界，需要跳跃（进入下一层）
if (i == curEnd) {
jumps++;
curEnd = farthest;
// 如果已经能到达终点，提前结束
if (curEnd >= n - 1) break;
}
}
return jumps;
}
}时间复杂度：O(n)，空间复杂度：O(1)。
我在 LeetCode 提交，运行时间 0ms，击败 100% 的 Java 用户。
算法流程
四、举一反三
同类型题目
LeetCode 1345. 跳跃游戏 IV
数组里的每个元素可以向任意相同值的位置跳，问最少跳几步到达末尾。BFS，把相同值的位置预先聚合到哈希表，BFS 时同时考虑向前一步、向后一步、跳到相同值的所有位置。
LeetCode 1654. 到家的最少跳跃次数
有禁区，正向跳的同时可以后退，求最少步数到达终点。BFS。
LeetCode 1340. 跳跃游戏 V（付费题）
矩阵版跳跃，每次可以跳到比当前低的相邻柱子。DFS + 记忆化。
贪心 vs DP 的选择原则
遇到"跳跃/到达"类型的题目：
- 问"能否到达"：贪心，维护 maxReach，O(n) O(1)
- 问"最少跳几步"：BFS 贪心，维护层边界，O(n) O(1)
- 问"所有到达路径数"或"带额外约束"：可能需要 DP 或 BFS
结论： 对于跳跃游戏的"能否到达"和"最少步数"这两个基本问题，贪心比 DP 更优（时间相同或更好，空间更省）。DP 适合"带状态的最优化"（如最大得分、最少花费），贪心适合"简单的最优化"（局部最优推全局最优的情景）。
五、踩坑实录
坑一：LeetCode 45 中遍历范围是 n-1 还是 n
现象： 某些用例（比如 [2,3,1,1,4]）返回结果不对，或者对最后一个元素也做了跳跃判断。
原因： 遍历到最后一个元素 n-1 时，我们已经到达了，不需要再跳了。如果遍历范围是 i < n，可能会多做一次 jumps++。
解法： 遍历范围是 i < n-1，不遍历最后一个元素。
坑二：LeetCode 55 中 maxReach 判断时机
现象： 某些输入下，nums = [0]，期望 true，但代码可能因为 i = 0 > maxReach = 0 而返回 false。
原因： 判断 i > maxReach 时，当 i = 0, maxReach = 0，0 > 0 为 false，不触发 return false，正确。但如果写成 i >= maxReach，就会错误地对起始点触发。
解法： 判断条件必须是严格 >，不是 >=。位置 0 本身就是可达的（起点），maxReach 初始为 0 表示至少能到 0 位置。
坑三：DP 解法中初始值设为 0 导致漏更新
现象： DP 解法中，dp[0]=0 初始化，但其他 dp[i] 初始化为 0 而不是 Integer.MAX_VALUE，导致即使没有更新，dp[i]=0 也参与了后续计算，答案偏小。
解法： Arrays.fill(dp, Integer.MAX_VALUE) 初始化所有位置为不可达，然后 dp[0] = 0，更新时用 min 取最小值，注意判断 dp[j] != Integer.MAX_VALUE 防止溢出。
六、总结
跳跃游戏系列展示了贪心算法的精髓：对于"到达"和"最短路径"这类问题，局部维护可达范围（maxReach）和层边界（curEnd），不需要存储每个位置的完整历史状态。
三条核心要点：
LeetCode 55 的贪心核心：维护全局最远可达位置 maxReach，遍历时如果当前位置 > maxReach，就是走不到这里。
LeetCode 45 的 BFS 贪心核心：把每次跳跃视为 BFS 的一层，
curEnd是当前层边界，farthest是下一层能到达的最远位置，到达curEnd时触发跳跃。跳跃游戏类题目先想贪心，如果贪心不够用（带额外约束、需要路径记录）再考虑 DP 或 BFS。一般来说，能贪心解的题目用 DP 也能解，但贪心更简洁高效。
延伸思考：
跳跃游戏的 BFS 思维在"最少操作步数"类问题里非常普遍：字符串变换（LeetCode 127 单词接龙）、骑士移动（国际象棋）、地图最短路径，这些都是 BFS 逐层遍历找最短路。跳跃游戏 II 的贪心可以看作在特殊结构（线性序列）上的 BFS 最优化。