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

描述 给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。请你判断最少跳几次能跳到数组最后一个位置。 1.如果跳不到数组最后一个位置或者无法跳跃(即数组长度为0)，请返回-1 2.数据保证返回的结果不会超过整形范围，即不会超过231−12^{31}-1231−1

数据范围: 0<=nums.length<=1050<=nums.length<=10^50<=nums.length<=105 0<=nums[i]<=10000<=nums[i]<=10000<=nums[i]<=1000 输入描述： 第一行输入一个正整数 n 表示数组 nums的长度 第二行输入 n 个整数，表示数组 nums 的内容 输出描述： 输出最少跳几次到最后一个位置 示例1 输入：

7 2 1 3 3 0 0 100

输出：

3

说明：

首先位于nums[0]=2，然后可以跳2步，到nums[2]=3的位置，step=1 再跳到nums[3]=3的位置，step=2 再直接跳到nums[6]=100，可以跳到最后，step=3，返回3

示例2 输入：

7 2 1 3 2 0 0 100

输出：

-1

#include<vector>
 
using namespace std;
 
class Solution {
    public:
    int minupgame3(vector<int> &nums){
         
        vector<int>dp(nums.size(),100000000);// 注意这里最好不用 INT32_MAX  容易 计算错误
        dp[0] =0;
         
        for (int i = 0;i< nums.size();i++){
            for (int j =i+1;j<= i+ nums[i] && j<nums.size();j++){
             
                    dp[j] = min (dp[j], dp[i] +1);

            }
        }
         
        return dp[nums.size()-1]==100000000 ? -1: dp[nums.size()-1];
         
    }
};
 
int main(){
    int val, n;
    cin >> n;
     
    vector<int>nums(n);
    for (int i =0; i<n;i++){
        cin >> val;
        nums[i] = val;
    }
    Solution solu;
    cout<< solu.minupgame3(nums) <<endl;
    return 0;
}