贪心算法2：跳跃游戏问题

引言

在上一篇文章中，我们学习了贪心算法的经典问题——区间调度问题。今天我们将探讨另一个有趣的贪心问题：跳跃游戏。

跳跃游戏问题不仅在算法面试中频繁出现，而且能够很好地展示贪心算法从暴力解法到优化解法的思维过程。通过这个问题，我们将学习如何逐步优化算法，找到最优的贪心策略。

问题描述

跳跃游戏 I (LeetCode 55)

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

示例 1：

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

示例 2：

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

跳跃游戏 II (LeetCode 45)

给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

示例：

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

解法一：跳跃游戏 I - 能否到达终点

思路分析

我们需要判断是否能到达最后一个位置。关键思想：维护一个能够到达的最远位置。

贪心策略：

1. 遍历数组，不断更新能够到达的最远位置
2. 如果当前位置超过了最远位置，说明无法继续前进
3. 如果最远位置 >= 数组长度-1，说明可以到达终点

代码实现 - 跳跃游戏 I

Java 代码

public class JumpGame {
    
    /**
     * 跳跃游戏 I - 判断能否到达最后一个位置
     * @param nums 非负整数数组
     * @return 能否到达最后一个位置
     */
    public static boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        
        int maxReach = 0;  // 能够到达的最远位置
        
        for (int i = 0; i < nums.length; i++) {
            // 如果当前位置超过了最远可达位置，无法继续
            if (i > maxReach) {
                return false;
            }
            
            // 更新最远可达位置
            maxReach = Math.max(maxReach, i + nums[i]);
            
            // 如果已经可以到达或超过最后一个位置
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        
        return maxReach >= nums.length - 1;
    }
    
    /**
     * 优化版本：倒序遍历
     * 从后往前找，看能否一步步推到起点
     */
    public static boolean canJumpBackward(int[] nums) {
        int lastPos = nums.length - 1;
        
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        
        return lastPos == 0;
    }
}

Python 代码

def can_jump(nums):
    """
    跳跃游戏 I - 判断能否到达最后一个位置
    :param nums: List[int] 非负整数数组
    :return: bool 能否到达最后一个位置
    """
    if not nums:
        return False
    
    max_reach = 0  # 能够到达的最远位置
    
    for i in range(len(nums)):
        # 如果当前位置超过了最远可达位置，无法继续
        if i > max_reach:
            return False
        
        # 更新最远可达位置
        max_reach = max(max_reach, i + nums[i])
        
        # 如果已经可以到达或超过最后一个位置
        if max_reach >= len(nums) - 1:
            return True
    
    return max_reach >= len(nums) - 1


def can_jump_backward(nums):
    """
    优化版本：倒序遍历
    从后往前找，看能否一步步推到起点
    """
    last_pos = len(nums) - 1
    
    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= last_pos:
            last_pos = i
    
    return last_pos == 0

复杂度分析

• 时间复杂度：O(n)，只需遍历一遍数组
• 空间复杂度：O(1)，只使用常数额外空间

解法二：跳跃游戏 II - 最少跳跃次数

贪心策略与算法流程

这个问题要求找到最少的跳跃次数。我们可以用贪心策略：在每一步中选择能够跳到最远位置的方案。

关键概念：

• currentEnd：当前跳跃能到达的边界
• farthest：下一跳能到达的最远位置
• jumps：跳跃次数

算法流程：

1. 遍历数组（不包括最后一个元素）
2. 不断更新下一跳能到达的最远位置
3. 当到达当前跳跃边界时，必须进行下一跳

代码实现 - 跳跃游戏 II

Java 代码 - 跳跃游戏 II

public class JumpGameII {
    
    /**
     * 跳跃游戏 II - 最少跳跃次数
     * @param nums 非负整数数组
     * @return 最少跳跃次数
     */
    public static int jump(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        
        int jumps = 0;         // 跳跃次数
        int currentEnd = 0;    // 当前跳跃的边界
        int farthest = 0;      // 下一跳能到达的最远位置
        
        // 注意：不需要访问最后一个元素
        for (int i = 0; i < nums.length - 1; i++) {
            // 更新下一跳能到达的最远位置
            farthest = Math.max(farthest, i + nums[i]);
            
            // 到达当前跳跃的边界，需要进行下一跳
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                
                // 如果已经可以到达或超过最后一个位置，提前结束
                if (currentEnd >= nums.length - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
    
    /**
     * 动态规划解法（用于对比）
     * 时间复杂度：O(n²)，空间复杂度：O(n)
     */
    public static int jumpDP(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }
        
        return dp[n - 1];
    }
}

Python 代码 - 跳跃游戏 II

def jump(nums):
    """
    跳跃游戏 II - 最少跳跃次数（贪心算法）
    :param nums: List[int] 非负整数数组
    :return: int 最少跳跃次数
    """
    if not nums or len(nums) <= 1:
        return 0
    
    jumps = 0          # 跳跃次数
    current_end = 0    # 当前跳跃的边界
    farthest = 0       # 下一跳能到达的最远位置
    
    # 注意：不需要访问最后一个元素
    for i in range(len(nums) - 1):
        # 更新下一跳能到达的最远位置
        farthest = max(farthest, i + nums[i])
        
        # 到达当前跳跃的边界，需要进行下一跳
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # 如果已经可以到达或超过最后一个位置，提前结束
            if current_end >= len(nums) - 1:
                break
    
    return jumps


def jump_dp(nums):
    """
    动态规划解法（用于对比）
    时间复杂度：O(n²)，空间复杂度：O(n)
    """
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0
    
    for i in range(n):
        for j in range(1, nums[i] + 1):
            if i + j < n:
                dp[i + j] = min(dp[i + j], dp[i] + 1)
    
    return dp[n - 1]

算法图解

nums = [2, 3, 1, 1, 4]
索引:    0  1  2  3  4

第1跳：从索引0出发，可以跳到索引1或2
      选择跳到索引1（因为从1出发能跳得更远）
      currentEnd = 2, farthest = 4

第2跳：在索引1，可以跳到索引2、3、4
      直接到达索引4（终点）
      jumps = 2

过程可视化：
[2, 3, 1, 1, 4]
 ^  ^  ^  ^  ^
 |  |__|  |  |
 |_____|__|__|
    第1跳  第2跳

时间空间复杂度

• 时间复杂度：O(n)，只需遍历一遍数组
• 空间复杂度：O(1)，只使用常数额外空间

测试用例

public class JumpGameTest {
    public static void main(String[] args) {
        // 测试跳跃游戏 I
        System.out.println("=== 跳跃游戏 I ===");
        int[] test1 = {2, 3, 1, 1, 4};
        System.out.println("输入: " + Arrays.toString(test1));
        System.out.println("能否到达: " + JumpGame.canJump(test1));  // true
        
        int[] test2 = {3, 2, 1, 0, 4};
        System.out.println("输入: " + Arrays.toString(test2));
        System.out.println("能否到达: " + JumpGame.canJump(test2));  // false
        
        // 测试跳跃游戏 II
        System.out.println("\n=== 跳跃游戏 II ===");
        int[] test3 = {2, 3, 1, 1, 4};
        System.out.println("输入: " + Arrays.toString(test3));
        System.out.println("最少跳跃次数: " + JumpGameII.jump(test3));  // 2
        
        int[] test4 = {2, 3, 0, 1, 4};
        System.out.println("输入: " + Arrays.toString(test4));
        System.out.println("最少跳跃次数: " + JumpGameII.jump(test4));  // 2
        
        int[] test5 = {1, 1, 1, 1, 1};
        System.out.println("输入: " + Arrays.toString(test5));
        System.out.println("最少跳跃次数: " + JumpGameII.jump(test5));  // 4
    }
}

if __name__ == "__main__":
    # 测试跳跃游戏 I
    print("=== 跳跃游戏 I ===")
    test1 = [2, 3, 1, 1, 4]
    print(f"输入: {test1}")
    print(f"能否到达: {can_jump(test1)}")  # True
    
    test2 = [3, 2, 1, 0, 4]
    print(f"输入: {test2}")
    print(f"能否到达: {can_jump(test2)}")  # False
    
    # 测试跳跃游戏 II
    print("\n=== 跳跃游戏 II ===")
    test3 = [2, 3, 1, 1, 4]
    print(f"输入: {test3}")
    print(f"最少跳跃次数: {jump(test3)}")  # 2
    
    test4 = [2, 3, 0, 1, 4]
    print(f"输入: {test4}")
    print(f"最少跳跃次数: {jump(test4)}")  # 2
    
    test5 = [1, 1, 1, 1, 1]
    print(f"输入: {test5}")
    print(f"最少跳跃次数: {jump(test5)}")  # 4

相关LeetCode题目

1. 55. 跳跃游戏

   • 判断能否到达终点

2. 45. 跳跃游戏 II

   • 求最少跳跃次数

3. 1306. 跳跃游戏 III

   • 可以向左或向右跳跃

4. 1345. 跳跃游戏 IV

   • 可以跳到相同值的位置

算法对比

方法	时间复杂度	空间复杂度	适用场景
贪心算法	O(n)	O(1)	跳跃游戏 I 和 II 的最优解
动态规划	O(n²)	O(n)	更复杂的变种问题
BFS	O(n²)	O(n)	需要记录路径的情况

关键思路总结

跳跃游戏 I 的贪心策略

核心思想：维护能够到达的最远位置

• 如果当前位置 > 最远位置，返回 false
• 不断更新最远位置
• 如果最远位置 >= 终点，返回 true

跳跃游戏 II 的贪心策略

核心思想：在必须跳跃时，选择能跳到最远的位置

• 维护两个变量：当前边界和下一跳最远位置
• 在遍历过程中不断更新下一跳最远位置
• 到达当前边界时，执行跳跃，更新边界

思维扩展

跳跃游戏问题的本质是区间覆盖问题：

1. 每个位置 i 可以覆盖的区间是 [i, i + nums[i]]
2. 问题转化为：这些区间能否覆盖整个数组
3. 贪心策略：始终选择能够延伸覆盖范围的最优方案

总结

通过跳跃游戏问题，我们学到了：

1. 贪心算法的优化思路：从动态规划的 O(n²) 优化到贪心的 O(n)
2. 问题抽象能力：将跳跃问题抽象为区间覆盖问题
3. 边界条件处理：注意遍历范围和提前终止条件
4. 多种解法对比：理解不同算法的适用场景

在下一篇文章中，我们将探讨加油站问题，这是另一个经典的贪心算法应用。

---

💡 思考题：

1. 如果允许向左跳跃，算法需要如何修改？
2. 如果数组中有负数（表示必须后退），问题会变成什么样？

📚 扩展阅读:

• LeetCode 跳跃游戏系列题目解析
• 贪心算法与动态规划的选择策略
• 区间覆盖问题的通用解法