跳跃游戏II

周子力大约 11 分钟教学文档动态规划

题目描述

题目理解

从索引0开始，目标是到达索引n-1
nums[i] 表示在位置i可以跳跃的最大长度
保证可以到达终点
目标：求最小跳跃次数（不是判断可行性）

暴力破解思路

暴力破解的思路主要基于穷举所有可能的跳跃路径，然后从中找出步数最少的那一条。具体思路如下：

问题定义：给定一个数组 nums，其中 nums[i] 表示在位置 i 可以跳跃的最大长度。目标是找到从索引 0 跳跃到数组末尾（索引 n-1）所需的最少步数。
暴力思路（递归/回溯）：
- 从起始位置 index = 0 开始。
- 对于当前位置 index，其最大跳跃步长为 nums[index]。这意味着下一步可以跳到 index+1, index+2, ..., index + nums[index] 中的任意一个位置（前提是不超出数组边界 n-1）。
- 暴力点：我们尝试所有这些可能的下一步位置。对于每一个可能的下一步位置 next_index，我们递归地调用函数，求解从 next_index 跳跃到末尾 n-1 所需的最少步数。
- 将当前这一步（+1）加上递归返回的最少步数，得到从当前位置 index 跳跃到末尾的一种总步数。
- 在所有从当前位置 index 出发的可能路径中，选择步数最少的那个，作为从 index 到达终点的最少步数。
- 递归的终止条件是：当 index 已经大于或等于 n-1 时，表示已经到达或超过终点，需要的步数为 0（如果恰好是 n-1）或者不需要再跳跃（如果超过了 n-1，但实际只需计算到 n-1，所以可以视为到达）。
实现方式：这种思路通常用递归（Recursion） 或 回溯（Backtracking） 来实现。它会显式地构建一棵决策树，树的每个节点代表一个位置，每个分支代表从该位置跳向下一个可能位置的决策。算法会遍历这棵决策树的所有路径，找到到达终点的最短路径。
时间复杂度：这种方法的效率非常低。在最坏情况下，每个位置都可能跳到后续的很多位置，导致递归树的分支因子很大，深度也可能达到 n。时间复杂度会是指数级的，例如 O(2^n) 或更高，因此对于较大的输入，这种方法是不现实的。

总结：暴力破解的核心就是“无脑尝试所有可能性”，然后取最优解。虽然逻辑上完全正确，但其效率低下，是学习高效算法（如贪心法、动态规划）之前的基准参考。它与贪心法（每步都做局部最优选择以达到全局最优）或动态规划（利用子问题最优解构建原问题最优解）形成了鲜明对比，凸显了后者的高效性。

贪心策略分析

核心思想

在每一步跳跃中，选择能够让我们在下一步跳得最远的位置。

关键洞察：我们不需要关心具体跳到哪个位置，而是关心当前这步能覆盖的范围内，下一步能到达的最远位置。

贪心策略设计

维护三个关键变量：

jumps：当前跳跃次数
current_end：当前跳跃能到达的最远边界
farthest：在当前边界内，下一步能到达的最远位置

算法逻辑：

遍历数组（除了最后一个元素，因为到达最后一个就结束了）
在当前边界内，不断更新 farthest = max(farthest, i + nums[i])
当到达当前边界的末尾时（i == current_end），必须进行一次跳跃：
- jumps += 1
- current_end = farthest
如果 current_end >= n-1，说明已经能到达终点

为什么贪心正确？

贪心选择性质：

在当前跳跃的覆盖范围内，我们选择能让下一步跳得最远的策略
这样做的结果是用最少的跳跃次数覆盖最大的距离
由于题目保证能到达终点，我们不需要担心无解情况

最优子结构：

最少跳跃次数 = 当前跳跃次数 + 剩余距离的最少跳跃次数
每次我们都做出当前最优的选择，不会影响后续的最优性

算法步骤

初始化 jumps = 0, current_end = 0, farthest = 0
遍历i从0到n-2（不需要处理最后一个元素）：
- 更新 farthest = max(farthest, i + nums[i])
- 如果 i == current_end，说明当前跳跃的覆盖范围到头了：
  - jumps += 1
  - current_end = farthest
  - 如果 current_end >= n-1，可以提前结束
返回 jumps

时间复杂度分析

时间复杂度：O(n) - 单次遍历数组
空间复杂度：O(1) - 只使用常数额外空间

Python代码实现

def jump(nums):
    """
    计算到达数组最后一个位置的最小跳跃次数
    
    Args:
        nums: List[int] - 每个位置的最大跳跃长度
    
    Returns:
        int - 最小跳跃次数
    """
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0          # 跳跃次数
    current_end = 0    # 当前跳跃能到达的最远边界
    farthest = 0       # 在当前边界内，下一步能到达的最远位置
    
    # 只需要遍历到 n-2，因为到达 n-1 就结束了
    for i in range(n - 1):
        # 更新在当前边界内能到达的最远位置
        farthest = max(farthest, i + nums[i])
        
        # 如果到达当前跳跃的边界，必须进行下一次跳跃
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # 如果已经能到达终点，可以提前结束
            if current_end >= n - 1:
                break
    
    return jumps

# 测试用例
if __name__ == "__main__":
    # 测试用例1
    nums1 = [2, 3, 1, 1, 4]
    print(f"输入: {nums1}")
    print(f"输出: {jump(nums1)}")  # 期望输出: 2
    
    # 测试用例2
    nums2 = [2, 3, 0, 1, 4]
    print(f"输入: {nums2}")
    print(f"输出: {jump(nums2)}")  # 期望输出: 2
    
    # 边界测试
    nums3 = [1]
    print(f"输入: {nums3}")
    print(f"输出: {jump(nums3)}")  # 期望输出: 0
    
    nums4 = [1, 1, 1, 1]
    print(f"输入: {nums4}")
    print(f"输出: {jump(nums4)}")  # 期望输出: 3
    
    nums5 = [5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0]
    print(f"输入: {nums5}")
    print(f"输出: {jump(nums5)}")  # 期望输出: 3

算法执行过程示例

示例1：`[2, 3, 1, 1, 4]`

初始: jumps=0, current_end=0, farthest=0

i=0: farthest = max(0, 0+2) = 2
     i == current_end(0), 所以 jumps=1, current_end=2

i=1: farthest = max(2, 1+3) = 4
i=2: farthest = max(4, 2+1) = 4  
     i == current_end(2), 所以 jumps=2, current_end=4 >= 4, 结束

返回: 2

示例2：`[2, 3, 0, 1, 4]`

初始: jumps=0, current_end=0, farthest=0

i=0: farthest = max(0, 0+2) = 2
     i == current_end(0), 所以 jumps=1, current_end=2

i=1: farthest = max(2, 1+3) = 4
i=2: farthest = max(4, 2+0) = 4
     i == current_end(2), 所以 jumps=2, current_end=4 >= 4, 结束

返回: 2

关键洞察

这个贪心算法的精妙之处在于：

分层跳跃：将跳跃过程分为多个"层"，每层对应一次跳跃
边界控制：用 current_end 标记当前层的边界，用 farthest 探索下一层的边界
延迟决策：在当前层内不断探索最优的下一层边界，直到必须跳跃时才做决定

这种方法避免了复杂的动态规划状态转移，用直观的贪心思想解决了最小跳跃次数问题。

注意事项与题目启发

需要注意的问题

1. 循环范围的精确性

for i in range(n - 1):  # 只遍历到 n-2

关键点：不需要处理最后一个元素（索引n-1）
原因：到达最后一个位置就结束了，不需要从那里再跳跃
常见错误：遍历到n-1会导致不必要的计算，虽然不影响结果但效率略低

2. 边界条件处理

if n <= 1:
    return 0

单元素数组：起始位置就是终点，跳跃次数为0
题目保证可达：不需要像跳跃游戏I那样检查可行性

3. 变量更新的顺序

farthest = max(farthest, i + nums[i])  # 先更新最远距离
if i == current_end:                   # 再检查是否需要跳跃
    jumps += 1
    current_end = farthest

必须先更新farthest，再判断是否到达边界
如果顺序颠倒，会在边界位置漏掉该位置的跳跃能力

4. 提前终止的时机

if current_end >= n - 1:
    break

优化点：一旦当前边界能覆盖终点，就可以提前结束
位置：必须在更新current_end之后立即检查

5. 算法逻辑的理解误区

不是每次都要跳跃：只有到达当前边界的末尾才跳跃
不是选择具体位置：算法不关心跳到哪个具体位置，只关心覆盖范围
贪心的延迟性：在当前跳跃范围内，我们延迟做决定，直到必须跳跃时才选择最优的下一步

6. 测试用例的特殊性

需要考虑多种情况：

一步到位：[5, 1, 1, 1] → 1次
逐步前进：[1, 1, 1, 1] → 3次
大跳跃后小跳跃：[10, 1, 1, 1] → 1次
复杂组合：[2, 3, 0, 1, 4] → 2次

7. 数据范围的考虑

题目保证 1 <= nums.length <= 10^4，算法O(n)完全满足
nums[i] 最大1000，i + nums[i] 不会溢出（Python无需担心）

8. 与跳跃游戏I的区别

跳跃游戏I：维护一个max_reach判断可行性
跳跃游戏II：维护current_end和farthest计算最小次数
容易混淆两个问题的解法，需要明确区分目标

题目的启发

1. 贪心算法的层次思维

分层策略：将问题分解为多个层次（每次跳跃为一层）
边界管理：用边界来划分不同的决策阶段
延迟决策：在当前层内收集所有信息，到边界时才做最优决策

2. 问题建模的抽象能力

从具体到抽象：不关心具体跳到哪，只关心覆盖范围
状态压缩：用两个边界变量替代复杂的路径记录
区间思维：将跳跃问题转化为区间覆盖问题

3. 算法设计的经典模式

这个问题展示了"BFS层次遍历"的贪心实现：

每次跳跃相当于BFS的一层
current_end 是当前层的右边界
farthest 是下一层的右边界
跳跃次数就是BFS的层数

4. 实际应用价值

网络跳数优化：路由协议中的最小跳数路径
游戏关卡设计：计算最少步数通关
资源分配：最少操作次数达到目标状态
系统设计：消息传递的最少中转次数

5. 编程思维的培养

逆向思考：从目标反推需要的最少步骤
范围思维：用区间而不是点来思考问题
效率意识：O(n)解法比动态规划O(n²)更优雅

6. 算法复杂度的权衡

时间效率：线性时间解决最优化问题
空间效率：常数空间，无需额外数据结构
可读性：代码简洁，逻辑清晰

7. 扩展思考方向

这个问题可以引申出更多变种：

带权重的跳跃：每次跳跃有不同代价，求最小总代价
不可达情况：需要同时判断可行性和最小次数
双向跳跃：可以向前或向后跳
多目标跳跃：需要访问多个特定位置
动态跳跃：跳跃能力随时间变化

8. 面试价值

经典程度：这是贪心算法和BFS思想结合的经典面试题
考察维度：
- 问题分析能力
- 算法设计能力
- 边界处理能力
- 优化思维能力
延伸性强：可以自然过渡到图论、动态规划等问题

9. 学习方法论

对比学习：与跳跃游戏I对比，理解问题变种的解法差异
手动模拟：通过小例子理解算法的执行过程
模式识别：识别"层次遍历"和"边界管理"的通用模式

10. 工程实践启示

简单优于复杂：贪心解法比动态规划更简洁高效
提前终止：在满足条件时及时结束，提高效率
防御性编程：虽然题目保证可达，但实际项目中要考虑异常情况

这个题目完美展示了如何将一个看似需要复杂搜索的问题，通过巧妙的贪心策略转化为简洁高效的线性算法。它告诉我们：有时候解决问题的关键不在于算法的复杂度，而在于对问题本质的深刻理解。