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

1.簡述：

描述

給定一個非負整數數組nums，假定最開始處于下标為0的位置，數組裡面的每個元素代表下一跳能夠跳躍的最大長度。請你判斷最少跳幾次能跳到數組最後一個位置。

1.如果跳不到數組最後一個位置或者無法跳躍(即數組長度為0)，請傳回-1

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

資料範圍:

輸入描述：

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

public class Main{

    public static int process2(int[]arr,int n){
        int step=0;
        int cur=0;
        int next=0;
        for(int i=0;i<n;i++){
            if(cur<i){
                step++;
                cur=next;
                if(cur<i)
                    return -1;
            }
            next=Math.max(next,i+arr[i]);
        }
        return step;
    }



    
    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(process2(arr,n));
        }
    }
}