题解 | 跳跃游戏(三)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minJumpStep (int[] nums) {
        // write code here
        //定于dp[i]表示到达nums[i]所需的最少跳跃次数
        if(nums.length==0) return -1;
        int[] dp = new int[nums.length+1];
        //这里定义为MAX_VALUE-1是因为后面的dp[i]+1可能会溢出！
        Arrays.fill(dp,Integer.MAX_VALUE-1);
        dp[0] = 0;
        //遍历每个元素，看它所能到达的位置
        for(int i=0;i<nums.length;i++){
            if(dp[i]==-1) continue;
            for(int j=1;j<=nums[i];j++){
                if(i+j>=nums.length) break;
                dp[i+j] = Math.min(dp[i+j],dp[i]+1);
            }
        }
        if(dp[nums.length-1]==Integer.MAX_VALUE-1) return -1;
        return dp[nums.length-1];
    }
}