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

1.简述：

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

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

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

3.数据保证返回的结果不会超过整形范围，即不会超过

数据范围:

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

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

输出能获得的最多的积分

输入：

6
2 4 2 1 0 100

输出：

106

说明：

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

输入：

6
2 4 0 2 0 100

输出：

108

说明：

跳跃路径为：2=>4=>2=>100，总共为108

输入：

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));
        }
    }
}