技术学习分享_一航技术 技术资讯 #yyds干货盘点# 动态规划专题:跳跃游戏(二)

#yyds干货盘点# 动态规划专题:跳跃游戏(二)

广告位

1.简述:

描述

给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。

1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1

2.如果无法跳跃(即数组长度为0),也请返回-1

3.数据保证返回的结果不会超过整形范围,即不会超过#yyds干货盘点# 动态规划专题:跳跃游戏(二)

数据范围:

#yyds干货盘点# 动态规划专题:跳跃游戏(二)

#yyds干货盘点# 动态规划专题:跳跃游戏(二)

输入描述:

第一行输入一个正整数 n 表示数组 nums的长度

第二行输入 n 个整数,表示数组 nums 的所有元素的值

输出描述:

输出能获得的最多的积分

示例1

输入:

6
2 4 2 1 0 100

输出:

106

说明:

首先位于nums[0]=2,然后可以跳1步,到nums[1]=4的位置,积分=2+4=6,再跳到nums[5]=100的位置,积分=6+100=106
这样保证既能跳到数组最后一个元素,又能保证获取的积分最多

示例2

输入:

6
2 4 0 2 0 100

输出:

108

说明:

跳跃路径为:2=>4=>2=>100,总共为108

示例3

输入:

6
2 3 2 1 0 100

输出:

-1

说明:

跳不到最后一个位置,返回-1

2.代码实现:

public class Main{
public static int process(int[]arr,int n){
int pos=n-1;
int res=arr[pos];
for(int i=n-2;i>=0;i--){
if(arr[i]+i>=pos){
pos=i;
res+=arr[i];
}
}
if(pos==0)
return res;
return -1;
}

public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
if(n==0)
System.out.print(-1);
else{
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
System.out.print(process(arr,n));
}
}
}
本文来自网络,不代表技术学习分享_一航技术立场,转载请注明出处。

作者: 一航技术

上一篇
下一篇
广告位

发表回复

返回顶部