题解 | #跳跃游戏(三)#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minJumpStep(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) {
            return -1;
        }
        if(n == 1){
            return 0;
        }
        vector<int> dp(n, -1); //表示到达下标位置所需要的最小步数
        dp[0] = 0;
        vector<bool> used(n, false);  //表示是否到达下标所在位置
        used[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
                if(!used[j]) {
                    dp[j] = dp[i] + 1;
                    used[j] = true;
                    if(j == n-1){
                        return dp[j];
                    }
                }
            }
            if(dp[i] == -1) { //无法到达i位置
                break;
            }
        }
        return -1;
    }
};