描述 给定一个非负整数数组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<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int minupgame3(vector<int> &nums){
vector<int>dp(nums.size(),INT32_MAX);
dp[0] =0;
for (int i = 1;i< nums.size();i++){
for (int j =0;j<i;j++){
if ( j+nums[j] >= i){
dp[i] = min (dp[i], dp[j] +1);
}
}
}
return dp[nums.size()-1]==INT32_MAX ? -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;
}