【算法实践】跳跃游戏——计算到达终点的最小跳数

问题描述

给定一个非负数数组 arr[]，每个元素表示从该位置最多可向前跳跃的步数。
示例：

• 若 arr[i] = 3，则可以从位置 i 跳跃到 i+1、i+2 或 i+3。
• 若 arr[i] = 0，则无法从该位置向前跳跃。

任务：找到从数组第一个位置移动到最后一个位置所需的最小跳跃次数。
注意：若无法到达终点，返回 -1。

示例

输入: arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
输出: 3
解释:
第一次从第 1 个元素（值 1）跳到第 2 个元素（值 3）。
第二次从第 2 个元素跳到第 5 个元素（值 9）。
第三次从第 5 个元素跳到终点。

输入: arr = [1, 4, 3, 2, 6, 7]
输出: 2
解释:
第一次从第 1 个元素跳到第 2 个元素，第二次跳到终点。

输入: arr = [0, 10, 20]
输出: -1
解释: 无法从第一个位置跳跃。

方法 1：递归（时间复杂度 O(nⁿ)，空间复杂度 O(n)）

核心思想：递归遍历所有可能的跳跃路径，返回最小跳跃次数。

public class JumpGame {

    // 递归函数：计算从位置i到终点的最小跳跃次数 
    private static int minJumpsRecursive(int[] arr, int i) {
        // 终止条件：当前已到达或超过终点 
        if (i >= arr.length - 1) return 0;
        int minSteps = Integer.MAX_VALUE;

        // 遍历所有可能的跳跃步数（1到arr[i]步） 
        for (int j = 1; j <= arr[i]; j++) {
            int nextPos = i + j;
            // 递归计算从下一步到终点的最小跳跃次数 
            int steps = minJumpsRecursive(arr, nextPos);
            if (steps != Integer.MAX_VALUE) {
                minSteps = Math.min(minSteps, 1 + steps); // 当前跳跃+后续步数 
            }
        }
        return minSteps;
    }


    public static int minJumps(int[] arr) {
        int result = minJumpsRecursive(arr, 0);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        System.out.println(minJumps(arr)); // 输出：3
    }
}

1. 1. 1. 方法 2：动态规划（时间复杂度 O(n²)，空间复杂度 O(n)）

核心思想：自底向上填充 dp[i]，表示从 i 到终点的最小跳跃次数。

public class JumpGameDP {
    public static int minJumps(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n - 1] = 0; // 终点到终点的跳跃次数为0  
        // 从倒数第二个元素向前推导  
        for (int i = n - 2; i >= 0; i--) {
            // 最多可跳跃到的最远位置  
            int maxJump = Math.min(i + arr[i], n - 1);
            for (int j = i + 1; j <= maxJump; j++) {
                if (dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[j]); // 选择最小的跳跃次数  
                }
            }
        }
        return dp[0] == Integer.MAX_VALUE ? -1 : dp[0];
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 1, 3, 2, 6, 7, 6, 8, 9};        
       System.out.println(minJumps(arr)); // 输出：4
       int[] arr1 = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        System.out.println(minJumps(arr1)); // 输出：3

    }
}

说明：

• 初始化：dp[n-1] = 0（终点无需跳跃）。
• 填表顺序：从后向前，每个位置依赖后续位置的结果。
• 优势：无需递归栈，空间更优。

方法对比