leetcode 45.跳跃游戏II

https://leetcode.com/problems/jump-game-ii/

45.跳跃游戏 II

你被给了一个长度为 n 的整数数组 nums，索引从 0 开始。你最初位于 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 <= 10^4
• 0 <= nums[i] <= 1000
• 保证你可以到达 nums[n - 1]。

动态规划算法

创建一个用于存储状态的数组minStepNums，用于存储位置i跳到最后位置所需的最小步数minStepNums[i]，对i位置来说可以到达的位置是(i, i+nums[i]]，假设里面的位置j具备最小的minStepNums[j]，则对于i位置来说到达最后位置所需的最小步数为minStepNums[i]=minStepNums[j]+1
时间复杂度：O(n^2)

class Solution {
    public int jump(int[] nums) {
        int[] minStepNums = new int[nums.length];
        Arrays.fill(minStepNums, Integer.MAX_VALUE); // 初始化为最大值
        minStepNums[nums.length - 1] = 0;
        for (int i = nums.length - 2; i >= 0; i--) {
            int minStepNum = Integer.MAX_VALUE;
            for (int j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
                if (minStepNums[j] != Integer.MAX_VALUE) { // 为了防止溢出
                    minStepNum = Math.min(minStepNum, minStepNums[j] + 1);
                }
            }
            minStepNums[i] = minStepNum;
        }
        return minStepNums[0];
    }
}

贪心算法

记录跳跃次数steps的同时，记录当前跳跃次数可到的的最远位置currentMaxPos，一边移动当前位置，一边判断情况

1. 已经到达当前steps可到达的最远距离currentMaxPos，此时不得不跳跃一次，同时刷新currentMaxPos
   • currentMaxPos的刷新：已经走过的位置可以根据每个位置的最大跳远距离，计算出下一次跳跃的最远距离nextMaxPos，跳完之后用这个值刷新currentMaxPos就可以了
2. 还没到达currentMaxPos，可以跳可以不跳，但是不跳肯定是次数最少的

   class Solution {
       public int jump(int[] nums) {
           int steps = 0;
           int currentMaxPos = 0;
           int nextMaxPos = 0;
           for (int i = 0; i < nums.length - 1; i++) {
               nextMaxPos = Math.max(i + nums[i], nextMaxPos);
               if (i == currentMaxPos) {
                   steps++;
                   currentMaxPos = nextMaxPos;
               }
           }
           return steps;
       }
   }

   Q：加深一下，如果题目没有保证最后的位置一定可达，那怎么办？
   A：移动i之后先做i > currentMaxPos的判断，如果大于了，说明无法到达此位置，直接返回-1就可以了