样例不过 求条~
描述
给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。
1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1
2.如果无法跳跃(即数组长度为0),也请返回-1
3.数据保证返回的结果不会超过整形范围,即不会超过2^31−1
输入描述:
第一行输入一个正整数 n 表示数组 nums的长度
第二行输入 n 个整数,表示数组 nums 的所有元素的值
输出描述:
输出能获得的最多的积分
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int nums[2024];
int DP[2024];
void DP_(){
DP[0] = nums[0];
for(int i = 0; i < n; ++ i){
for(int j = i + 1; DP[i] && j < n && j < nums[i] + i + 1; ++ j){
DP[j] = max(DP[i] + DP[j], DP[j]);
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n; ++ i) cin >> nums[i];
DP_();
cout << (DP[n - 1] == 0 ? -1 : DP[n - 1]) << '\n';
}