【LeetCode】45. 跳跃游戏 II

链接：https://leetcode-cn.com/problems/jump-game-ii/description/

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

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

假设你总是可以到达数组的最后一个位置。

思路一：
利用动态规划的思路，构建一个stepMatrix[]数组，保存到达每个位置所需要的最小步数
从第一个位置开始，stepMatrix[0] = 0，将其所能到达的位置步数+1
然后一个一个位置的往后推，直到找到最后的位置。

但是这样的复杂度可能会达到O(n2), 因此进行优化，找到下一步能到达的最远位置的那个点，从这个能到达最远位置的点再重复上述步骤。

class Solution {
    public int jump(int[] nums) {
        int size = nums.length;
        
        // 初始化记录步数的矩阵
        int[] stepMatrix = new int[size];
        for(int i= 0; i<size; i++) {
            stepMatrix[i] = Integer.MAX_VALUE;   
        }
        
        stepMatrix[0] = 0;
        for(int i=0; i<size-1; ) {
            int nextPosition = i;  //下一个开始搜索的位置
            int maxPosition = 0;   //下一步可到达的最远位置
            for(int j=1; j<=nums[i]; j++) {
                //若超出范围，则已找到最小步数
                if(i+j >= size-1) {
                    return stepMatrix[i]+1;
                }
                //将可到达的位置的步数记录为i点的步数+1
                if(stepMatrix[i]+1 < stepMatrix[i+j]) {
                    stepMatrix[i+j] = stepMatrix[i] + 1;
                }
                //找出下一步可以到达的最远点maxPosition，及其前置位置nextPosition
                if(nums[i+j] +i+j > maxPosition) {
            
                    maxPosition = nums[i+j] +i+j;
                    nextPosition = i+j;
                }
               
            }
    
            //从nextPosition处继续执行循环
            i = nextPosition;
        }
        
        return stepMatrix[size-1];
    }
}

思路二：
利用BFS(广度优先)算法，将问题转化为图，广度优先遍历，即可快速找到，复杂度为O(n);

 int jump(int A[], int n) {
     if(n<2)return 0;
     int level=0,currentMax=0,i=0,nextMax=0;

     while(currentMax-i+1>0){       //nodes count of current level>0
         level++;
         for(;i<=currentMax;i++){   //traverse current level , and update the max reach of next level
            nextMax=max(nextMax,A[i]+i);
            if(nextMax>=n-1)return level;   // if last element is in level+1,  then the min jump=level 
         }
         currentMax=nextMax;
     }
     return 0;
 }