最小跳跃次数算法疑惑：代码结果与预期不符求解析

你的核心问题是误解了题目中的跳跃规则：每个位置的元素是「最大可跳跃长度」，不是必须跳这么多步——你可以选择跳1到该元素值之间的任意步数，而要找最少跳跃次数，关键是每次选择能让你跳得最远的中间点，而非盲目跳最大步数。

你的代码为什么得到6次跳跃？ #

你的代码逻辑是每次直接跳arr[i]步，对应路径是：
0 → 2（跳2步）→3（跳1步）→4（跳1步）→6（跳2步）→8（跳2步）→9（跳1步），总共6次。这是因为你没有选择更优的跳跃点，只是机械地跳最大步数。

正确的4次跳跃路径 #

针对输入arr[] = [2,3,1,1,2,4,2,0,1,1]，最少跳跃的路径是：

• 第1次：从索引0（值2）跳1步到索引1（值3）——这个位置能让你跳到最远的位置（1+3=4）
• 第2次：从索引1（值3）跳3步到索引4（值2）
• 第3次：从索引4（值2）跳1步到索引5（值4）——这个位置直接能跳到末尾（5+4=9）
• 第4次：从索引5（值4）跳4步到索引9（数组末尾）

正确的贪心解法代码 #

要实现最少跳跃次数，需要用贪心算法：每次在当前可到达的范围内，选择能跳得最远的位置作为下一个跳跃点，这样每次跳跃覆盖的范围最大，次数最少。代码如下：

int minJumps(int arr[], int n) {
    if (n <= 1) return 0;
    if (arr[0] == 0) return -1;
    
    int maxReach = arr[0]; // 当前能到达的最远位置
    int steps = arr[0];    // 当前跳跃范围内剩余的步数
    int jumps = 1;         // 跳跃次数
    
    for (int i = 1; i < n; i++) {
        if (i == n - 1) return jumps;
        
        // 更新能到达的最远位置
        maxReach = max(maxReach, i + arr[i]);
        steps--;
        
        // 当当前步数用完，必须再跳一次
        if (steps == 0) {
            jumps++;
            // 如果当前位置已经超过最远可达位置，说明无法到达末尾
            if (i >= maxReach) return -1;
            // 更新剩余步数为最远位置到当前索引的距离
            steps = maxReach - i;
        }
    }
    return -1;
}

内容的提问来源于stack exchange，提问作者doubtttttttttttttt