#yyds幹貨盤點# 動态規劃專題：跳躍遊戲(二)

1.簡述：

描述

給定一個非負整數數組nums，假定最開始處于下标為0的位置，數組裡面的每個元素代表下一跳能夠跳躍的最大長度，如果可以跳到數組最後一個位置，請你求出跳躍路徑中所能獲得的最多的積分。

1.如果能夠跳到數組最後一個位置，才能計算所獲得的積分，否則積分值為-1

2.如果無法跳躍(即數組長度為0)，也請傳回-1

3.資料保證傳回的結果不會超過整形範圍，即不會超過

資料範圍:

輸入描述：

第一行輸入一個正整數 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      

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