跳跃游戏系列：维护可达区间的贪心艺术

摘要

跳跃游戏（LeetCode 55 和 45）是贪心算法中最经典、最值得深度剖析的一对题目。55 题（判断能否到达终点）和 45 题（最少跳跃次数）乍看是两道独立的题，实则共享同一个贪心核心：维护当前可达的最远位置。本文不只给代码，而是从为什么动态规划解法存在但不必要，到如何从 BFS 的视角理解贪心解法的本质，再到严格的数学归纳法证明，层层深入，帮你真正掌握”可达范围维护”这一贪心模式。

第 1 章跳跃游戏的问题背景

1.1 LeetCode 55 题目

LeetCode 55 - Jump Game（中等）

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

判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。

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

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

1.2 LeetCode 45 题目

LeetCode 45 - Jump Game II（中等）

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换言之，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处。

返回到达 nums[n - 1] 的最少跳跃次数。测试用例保证可以到达 nums[n - 1]。

输入: nums = [2, 3, 1, 1, 4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2，从下标 0 跳到下标 1，然后跳 3 步到达数组的最后一个位置

输入: nums = [2, 3, 0, 1, 4]
输出: 2

1.3 两道题的关系

55 是”能不能到达”，45 是”最少跳几步”。45 是 55 的加强版：在 55 可以到达的前提下，求最少跳数。

从算法角度，两道题的贪心解法共享同一个核心变量 maxReach（当前能到达的最远位置），只是附加的统计逻辑不同。

第 2 章 LeetCode 55：能否到达终点

2.1 动态规划解法（先理解 DP，再理解贪心）

在理解贪心之前，先看 DP 解法，因为贪心是从 DP 简化来的。

设 canReach[i] = true 表示从 nums[0] 出发，能否到达位置 i。

转移方程：canReach[i] = true 当且仅当存在某个 j < i，使得 canReach[j] = true 且 j + nums[j] >= i。

// DP 解法，O(n²)
public boolean canJump(int[] nums) {
    int n = nums.length;
    boolean[] canReach = new boolean[n];
    canReach[0] = true;
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (canReach[j] && j + nums[j] >= i) {
                canReach[i] = true;
                break;
            }
        }
    }
    return canReach[n - 1];
}

时间复杂度： $O (n^{2})$ ，内层循环遍历所有可能的前驱位置。

DP 的冗余：注意到 canReach[i] = true 当且仅当 i <= max{j + nums[j] : canReach[j] = true, j < i}。所以我们只需要维护一个值：maxReach = max{j + nums[j] : canReach[j] = true, j <= 当前位置}。

2.2 贪心解法：维护最远可达位置

关键简化：

canReach[i] = true 当且仅当 i <= maxReach（其中 maxReach 是截至位置 i-1 可到达的最远位置）
如果 i <= maxReach，则从 i 可以跳到 i + nums[i]，更新 maxReach = max(maxReach, i + nums[i])
如果某时刻 i > maxReach，说明位置 i 无法到达，后续位置也无法到达

// 贪心解法，O(n)
public boolean canJump(int[] nums) {
    int maxReach = 0;  // 当前能到达的最远位置
 
    for (int i = 0; i < nums.length; i++) {
        // 如果当前位置 i 超过了最远可达位置，说明无法到达 i
        if (i > maxReach) return false;
 
        // 从位置 i 出发，最远能到 i + nums[i]，更新 maxReach
        maxReach = Math.max(maxReach, i + nums[i]);
    }
 
    // 走完整个数组都没有遇到"无法到达"的情形，能到达终点
    return true;
}

为什么这是 $O (n)$ ：只有一层线性扫描，每个位置处理 $O (1)$ 。

2.3 贪心正确性证明（数学归纳法）

命题：设 maxReach 是 canJump 贪心算法扫描到位置 i 时维护的最远可达位置。命题 P(i)：从位置 0 出发，能到达的最远位置恰好是 maxReach。

基础情形（i = 0）：maxReach = nums[0]，从位置 0 能到达的最远位置是 nums[0]。P(0) 成立。

归纳步骤：假设 P(i-1) 成立，即扫描到 i-1 时的 maxReach 是从 0 出发能到达的真实最远位置。

现在到达位置 i：

若 i > maxReach（P(i-1) 下的 maxReach）：位置 i 不可达（由 P(i-1) 知，从 0 最远只能到 maxReach < i），返回 false。正确。
若 i <= maxReach：位置 i 可达，从 i 可以到达 i + nums[i]，新的最远可达位置是 max(maxReach, i + nums[i])。P(i) 成立。

结论：命题 P(i) 对所有 $i$ 成立，maxReach 始终准确反映从 0 出发能到达的最远位置。因此，若扫描完整个数组都没有 i > maxReach，说明所有位置（包括最后一个）都可达。

第 3 章 LeetCode 45：最少跳跃次数

3.1 动态规划解法（先理解，再简化）

设 minJumps[i] = 从位置 0 到达位置 i 的最少跳跃次数。

// DP 解法，O(n²)
public int jump(int[] nums) {
    int n = nums.length;
    int[] minJumps = new int[n];
    Arrays.fill(minJumps, Integer.MAX_VALUE);
    minJumps[0] = 0;
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (minJumps[j] != Integer.MAX_VALUE && j + nums[j] >= i) {
                minJumps[i] = Math.min(minJumps[i], minJumps[j] + 1);
            }
        }
    }
    return minJumps[n - 1];
}

这是 $O (n^{2})$ 的，对 $n = 1 0^{4}$ 可能超时。贪心解法是 $O (n)$ 的。

3.2 BFS 视角：层次分明的跳跃

理解贪心解法的最直观方式是BFS 类比：

把每个位置想象成一个图节点，位置 j 到位置 k（只要 k <= j + nums[j]）有一条有向边
求从位置 0 到位置 n-1 的最短路（BFS，边权为 1）

BFS 的特点是层次扩展：第 0 层是 {0}（出发点），第 1 层是第一跳能到的所有位置，第 2 层是第二跳能到的所有位置，……第 k 层是恰好需要 k 次跳跃才能到达的所有位置。答案是终点所在的层号。

贪心的等价性：在 BFS 中，每一”层”是从上一层的所有位置能到达的所有新位置。因为每个位置 j 能到达 [j+1, j+nums[j]] 的所有位置，这一层的最远边界是 max{j + nums[j] : j 在当前层}。

所以，BFS 的每一层可以用”最远右边界”来紧凑地表示：

层次	起点范围	该层最远右边界
第 0 层	`[0, 0]`	`nums[0]`
第 1 层	`[1, nums[0]]`	`max{j+nums[j] : 1<=j<=nums[0]}`
第 2 层	`[nums[0]+1, 第1层最远]`	`max{j+nums[j] : j 在第1层}`
…	…	…

3.3 贪心实现

public int jump(int[] nums) {
    int n = nums.length;
    int jumps = 0;       // 跳跃次数
    int currentEnd = 0;  // 当前层的末尾（当前跳跃覆盖的最远位置）
    int farthest = 0;    // 下一层的末尾（下一跳能到达的最远位置）
 
    // 注意：只扫描到 n-2，不包括最后一个元素
    // 因为当 i == n-1 时，我们已经到达终点，不需要再跳
    for (int i = 0; i < n - 1; i++) {
        // 更新下一层的末尾（从当前位置 i 出发的最远可达位置）
        farthest = Math.max(farthest, i + nums[i]);
 
        // 当 i 到达当前层的末尾时，必须跳一次（进入下一层）
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
 
            // 已经能到达终点，提前退出
            if (currentEnd >= n - 1) break;
        }
    }
 
    return jumps;
}

关键设计点：

currentEnd：当前跳跃的”覆盖范围”末尾。扫描到 currentEnd 时，必须再跳一次（进入下一跳的覆盖范围）。
farthest：在当前层扫描过程中，持续更新”下一跳能到达的最远位置”。当 i == currentEnd 时，farthest 就是下一层的末尾。
为什么循环到 n-2 而不是 n-1：如果 n-1 已经在 currentEnd 以内，我们不需要再跳一次（已经到达终点）。如果循环到 n-1，当 i == n-1 == currentEnd 时，会错误地多加一次 jumps。

3.4 手工演示

以 nums = [2, 3, 1, 1, 4]，n = 5 为例：

i	nums[i]	farthest	i == currentEnd?	操作
0	2	max(0, 0+2)=2	0==0，是	jumps=1, currentEnd=2
1	3	max(2, 1+3)=4	1≠2	继续扫描
2	1	max(4, 2+1)=4	2==2，是	jumps=2, currentEnd=4
（currentEnd=4 >= n-1=4，break）

最终 jumps = 2，正确。

以 nums = [2, 3, 0, 1, 4] 为例：

i	nums[i]	farthest	i == currentEnd?	操作
0	2	max(0, 0+2)=2	0==0，是	jumps=1, currentEnd=2
1	3	max(2, 1+3)=4	1≠2	继续扫描
2	0	max(4, 2+0)=4	2==2，是	jumps=2, currentEnd=4
（currentEnd=4 >= n-1=4，break）

最终 jumps = 2，正确。（注意 nums[2] = 0 没有问题，因为跳一次能直接到达终点）

3.5 贪心正确性证明（交换论证法）

命题：贪心解法给出的跳跃次数是最少的。

证明：设 OPT 是某个最优解，跳跃次数为 $k$ ，经过位置序列 $0 = p_{0} \leq p_{1} \leq ... \leq p_{k} = n - 1$ 。贪心解 GRD 的跳跃次数为 $m$ ，经过位置序列 $0 = q_{0} \leq q_{1} \leq ... \leq q_{m} = n - 1$ 。

关键引理：对所有 $t \leq k$ ，有 $q_{t} \geq p_{t}$ （贪心每一步能到达的位置不比 OPT 更差）。

引理证明（归纳）：

$t = 0$ ： $q_{0} = p_{0} = 0$ ，成立。
假设 $q_{t - 1} \geq p_{t - 1}$ ，证明 $q_{t} \geq p_{t}$ 。
- 贪心第 $t$ 跳的范围是 $[q_{t - 1}, farthest]$ ，其中 farthest = max{j+nums[j] : q_{t-1-1}+1 <= j <= q_{t-1}}（即从上一层的所有位置能到达的最远位置）
- OPT 第 $t$ 跳是从 $p_{t - 1}$ 出发，到达 $p_{t} \leq p_{t - 1} + n u m s [p_{t - 1}]$
- 由于 $q_{t - 1} \geq p_{t - 1}$ ，贪心在 $[..., q_{t - 1}]$ 这一层扫描时，会扫描到 $p_{t - 1}$ （因为 $p_{t - 1} \leq q_{t - 1}$ ），因此贪心的 farthest >= p_{t-1} + nums[p_{t-1}] >= p_t
- 所以 $q_{t} = farthest \geq p_{t}$ ，引理成立

由引理， $q_{k} \geq p_{k} = n - 1$ ，所以贪心在第 $k$ 步或更早（ $\leq k$ 步）就能到达终点。因此 $m \leq k$ ，即贪心跳跃次数不多于最优解。又显然 $m \geq k$ （最优解就是最少的），所以 $m = k$ ，贪心解是最优的。

第 4 章两道题的深度对比

4.1 关键变量的对应关系

变量	LeetCode 55	LeetCode 45	含义
`maxReach`	核心变量，单一更新	对应 `farthest`（下一层末尾）	当前能到达的最远位置
层分界	无（不需要计数跳次）	`currentEnd`（当前层末尾）	触发跳跃计数的边界
答案	`maxReach >= n-1`	`jumps`	—

4.2 为什么 45 需要”层”的概念而 55 不需要

55 只问”能不能到”，不关心跳几次，所以维护一个 maxReach 即可，只要 maxReach >= n-1 就能到达。

45 问”最少跳几次”，需要计数跳跃次数。BFS 中每次从一层扩展到下一层就是跳了一次，所以需要维护当前层的边界 currentEnd，每当扫描到边界时计数并更新到下一层的边界 farthest。

4.3 常见错误分析

错误 1（LeetCode 45）：循环到 n-1 而非 n-2

// 错误写法
for (int i = 0; i < n; i++) {  // 应该是 i < n - 1
    farthest = Math.max(farthest, i + nums[i]);
    if (i == currentEnd) {
        jumps++;
        currentEnd = farthest;
    }
}

当 i = n-1 且 n-1 == currentEnd 时，会多执行一次 jumps++，结果偏大 1。

错误 2（LeetCode 55）：更新 maxReach 前就检查 i > maxReach

// 错误写法
for (int i = 0; i < nums.length; i++) {
    maxReach = Math.max(maxReach, i + nums[i]);  // 先更新
    if (i > maxReach) return false;  // 再检查（此时用的是已更新的 maxReach，逻辑错误）
}

i > maxReach 应该在更新 maxReach 之前检查（检查的是”能否到达位置 i”，不是”能否到达 i+nums[i]”）。

正确写法：先检查 if (i > maxReach) return false，再更新 maxReach = Math.max(maxReach, i + nums[i])。

第 5 章扩展思考：跳跃游戏的变体

5.1 Jump Game III（LeetCode 1306）

变体：从任意初始位置出发，每个位置 i 可以跳到 i + nums[i] 或 i - nums[i]（双向跳），判断能否跳到值为 0 的位置。

这是图的可达性问题，用 BFS 或 DFS 解决，不是贪心。说明并非所有”跳跃游戏”都适合贪心——贪心仅在单向、单调（只能向右跳）的情形下有效。

5.2 Jump Game VII（LeetCode 1871）

变体：字符串上的跳跃，带有区间约束的跳跃范围。这类变体通常用差分数组或线段树优化，不再是简单贪心。

5.3 跳跃游戏的贪心适用条件

以上变体让我们反思：原版跳跃游戏为什么贪心有效？

根本原因：跳跃是单调向右的，且从任意可达位置 j 能到达的范围 [j+1, j+nums[j]] 具有”包含性”——maxReach 单调不减。这保证了”贪心维护最远位置”的正确性。

一旦跳跃方向不固定（可以左右），或者可达范围受到额外约束（非线性），单纯维护最远位置就不够了，需要更复杂的搜索或 DP。

第 6 章本文核心结论

两道题共享”维护最远可达位置”的贪心核心：55 维护 maxReach，45 在此基础上增加 currentEnd 来计数层次（跳跃次数）。
BFS 类比是理解 45 的最直观视角：每一”层”对应需要相同跳跃次数的位置集合，贪心用最远右边界紧凑表示每一层，无需显式存储所有节点。
45 的细节陷阱：循环到 n-2：循环条件是 i < n-1（不包括最后一个元素），否则会多计一次跳跃。
严格证明需要”引理：贪心每步不差于最优解”：这是交换论证的一种形式——证明贪心能始终”至少和最优解一样好”，从而贪心解就是最优解。
贪心的适用条件：单向跳跃 + 可达范围单调延伸。一旦引入双向跳跃或复杂约束，需改用 BFS/DP。

汀的知识碎片

文章导航

07 跳跃游戏系列：维护可达区间的贪心艺术

跳跃游戏系列：维护可达区间的贪心艺术

摘要

第 1 章跳跃游戏的问题背景

1.1 LeetCode 55 题目

1.2 LeetCode 45 题目

1.3 两道题的关系

第 2 章 LeetCode 55：能否到达终点

2.1 动态规划解法（先理解 DP，再理解贪心）

2.2 贪心解法：维护最远可达位置

2.3 贪心正确性证明（数学归纳法）

第 3 章 LeetCode 45：最少跳跃次数

3.1 动态规划解法（先理解，再简化）

3.2 BFS 视角：层次分明的跳跃

3.3 贪心实现

3.4 手工演示

3.5 贪心正确性证明（交换论证法）

第 4 章两道题的深度对比

4.1 关键变量的对应关系

4.2 为什么 45 需要”层”的概念而 55 不需要

4.3 常见错误分析

第 5 章扩展思考：跳跃游戏的变体

5.1 Jump Game III（LeetCode 1306）

5.2 Jump Game VII（LeetCode 1871）

5.3 跳跃游戏的贪心适用条件

第 6 章本文核心结论

On this page

汀的知识碎片

文章导航

07 跳跃游戏系列：维护可达区间的贪心艺术

跳跃游戏系列：维护可达区间的贪心艺术

摘要

第 1 章 跳跃游戏的问题背景

1.1 LeetCode 55 题目

1.2 LeetCode 45 题目

1.3 两道题的关系

第 2 章 LeetCode 55：能否到达终点

2.1 动态规划解法（先理解 DP，再理解贪心）

2.2 贪心解法：维护最远可达位置

2.3 贪心正确性证明（数学归纳法）

第 3 章 LeetCode 45：最少跳跃次数

3.1 动态规划解法（先理解，再简化）

3.2 BFS 视角：层次分明的跳跃

3.3 贪心实现

3.4 手工演示

3.5 贪心正确性证明（交换论证法）

第 4 章 两道题的深度对比

4.1 关键变量的对应关系

4.2 为什么 45 需要”层”的概念而 55 不需要

4.3 常见错误分析

第 5 章 扩展思考：跳跃游戏的变体

5.1 Jump Game III（LeetCode 1306）

5.2 Jump Game VII（LeetCode 1871）

5.3 跳跃游戏的贪心适用条件

第 6 章 本文核心结论

On this page

第 1 章跳跃游戏的问题背景

第 4 章两道题的深度对比

第 5 章扩展思考：跳跃游戏的变体

第 6 章本文核心结论