给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i] 

  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

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

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

 提示:

  • 1 <= nums.length <= 104

  • 0 <= nums[i] <= 1000

  • 题目保证可以到达 nums[n-1]

思路

  • 动态规划

  • 贪心算法

代码

  • 动态规划

class Solution {
    //45. 跳跃游戏 II
    public int jump(int[] nums) {
        //动态规划
        int len = nums.length;
        int[] counts = new int[len];
        int index = 0;
        for (int num : nums) {
            for (int i = index + 1; i <= index + num && i < len; i++) {//贪心优化这步
                if (counts[i] == 0) {
                    counts[i] = counts[index] + 1;
                }
            }
            index++;
        }
        return counts[len - 1];
    }
}

  • 贪心算法 

class Solution {
    //45. 跳跃游戏 II
    public int jump(int[] nums) {
        //动态规划
//        int len = nums.length;
//        int[] counts = new int[len];
//        int index = 0;
//        for (int num : nums) {
//            for (int i = index + 1; i <= index + num && i < len; i++) {//贪心优化这步
//                if (counts[i] == 0) {
//                    counts[i] = counts[index] + 1;
//                }
//            }
//            index++;
//        }
//        return counts[len - 1];
        //贪心算法
        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;
    }
}