计算数组中到达末尾的最小跳跃次数

1. 概述

在本教程中，我们将探讨如何从数组的起始位置出发，计算到达数组末尾所需的最小跳跃次数。我们将介绍三种不同的解决方案：朴素递归法、动态规划法和贪心算法。每种方法都有其适用场景和复杂度特点，最终我们会选择最优解。

2. 问题定义

给定一个由正整数组成的数组 A，其中每个元素表示从当前位置可以向右跳跃的最大步数。我们的目标是：从数组的第一个元素出发，计算到达数组末尾之后位置所需的最少跳跃次数。

来看一个示例：

jumps 1

以下是一些可能的跳跃路径：

2 → 1 → 7 → end
2 → 3 → 7 → end
2 → 3 → end

jumps 2

观察可知，最优路径是 2 → 3 → 4，跳跃次数为 2 次。

3. 朴素递归法（Brute Force）

3.1. 核心思想

尝试所有可能的跳跃路径，从中找出跳跃次数最少的一条路径。这是最直接的思路，但效率非常低。

3.2. 算法实现

int MinimumJumps(int[] A, int index) {
    if (index >= A.length - 1) {
        return 0;
    }

    int minJumps = Integer.MAX_VALUE;

    for (int i = 1; i <= A[index]; i++) {
        int nextJumps = MinimumJumps(A, index + i);
        if (nextJumps != Integer.MAX_VALUE) {
            minJumps = Math.min(minJumps, nextJumps + 1);
        }
    }

    return minJumps;
}

递归终止条件：当索引超过或等于数组长度时，说明已经到达终点，返回 0。
递归逻辑：从当前位置尝试所有可能的跳跃步数，递归计算后续路径的跳跃次数，并取最小值。

3.3. 复杂度分析

时间复杂度：最坏情况下为 O(M^N)
- N 是数组长度，M 是数组中最大跳跃值。
- 每个位置最多有 M 种跳跃选择，递归树深度为 N。
空间复杂度：O(1)（不考虑递归栈）

⚠️ 踩坑提醒：该方法在大数组时会严重超时，不适用于实际场景。

4. 动态规划法（Dynamic Programming）

4.1. 核心思想

使用动态规划来优化递归方法。我们定义 dp[i] 表示从位置 i 到达终点所需的最小跳跃次数。从后往前填充 dp 数组，利用已知的子问题解来求当前解。

4.2. 算法实现

int MinimumJumps(int[] A) {
    int n = A.length;
    int[] dp = new int[n];
    Arrays.fill(dp, Integer.MAX_VALUE);

    dp[n - 1] = 0; // 最后一个位置不需要跳跃

    for (int i = n - 2; i >= 0; i--) {
        int furthest = Math.min(i + A[i], n - 1);
        for (int j = i + 1; j <= furthest; j++) {
            if (dp[j] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }

    return dp[0];
}

初始化：最后一个位置跳跃次数为 0。
状态转移：dp[i] = min(dp[i + 1], dp[i + 2], ..., dp[i + A[i]]) + 1

4.3. 复杂度分析

时间复杂度：O(N * M)
- 每个位置最多尝试 M 次跳跃。
空间复杂度：O(N)
- 使用一个长度为 N 的数组存储中间结果。

✅ 优点：相比递归法，大大减少了重复计算。

⚠️ 踩坑提醒：当跳跃步数较大时，该方法仍有性能瓶颈。

5. 贪心算法（Greedy）

5.1. 核心思想

使用贪心策略，每次尽可能跳得更远。维护当前能到达的最远位置和剩余跳跃步数，一旦当前步数用完，就进行一次跳跃并更新可用步数。

5.2. 算法实现

int MinimumJumps(int[] A) {
    if (A.length <= 1) return 0;

    int maxReach = A[0];
    int steps = A[0];
    int jumps = 1;

    for (int i = 1; i < A.length; i++) {
        maxReach = Math.max(maxReach, i + A[i]);
        steps--;

        if (steps == 0) {
            jumps++;
            steps = maxReach - i;
        }
    }

    return jumps;
}

maxReach：当前能跳到的最远位置。
steps：当前跳跃剩余步数。
jumps：已跳跃次数。

5.3. 复杂度分析

时间复杂度：O(N)
- 只需遍历一次数组。
空间复杂度：O(1)
- 只使用了常数级变量。

✅ 优点：时间复杂度最低，适用于大规模数组。

✅ 推荐使用：在大多数实际场景中，这是最优解。

6. 总结

我们介绍了三种解决“到达数组末尾所需最小跳跃次数”的方法：

方法	时间复杂度	空间复杂度	是否推荐
递归法	O(M^N)	O(1)	❌
动态规划	O(N * M)	O(N)	✅
贪心算法	O(N)	O(1)	✅✅✅

最终推荐使用 贪心算法，它在时间效率和空间占用上都达到了最优水平，是解决此类问题的首选方案。

Persistence

REST

Security