跳跃游戏(三)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] array = new int[n];
            for(int i = 0; i < n; i++) {
                array[i] = in.nextInt();
            }
            if(n == 0) {
                System.out.println(-1);
            } else {
                int res = jumpingGame(array);
                System.out.println(res);
            }
        }
    }
    public static int jumpingGame(int[] array) {
        int n = array.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < array.length - 1; i++) {
            int temp = array[i];
            if(dp[i] == Integer.MAX_VALUE || temp == 0) {
                continue;
            }
            // 更新跳到 i + 1, i + 2 ... i + temp 所需跳数,
            // 如果 i + temp 大于 n - 1, 那么只需要更新到 n - 1 即可
            for(int j = 1; j <= temp; j++) {
                if(i + j < n) {
                // 如果 i+j 位置所需跳数为 Integer.MAX_VALUE,
                // 直接更新为 dp[i] + 1,否则就取 max(dp[i+j],dp[i]+1)
                    if(dp[i + j] != Integer.MAX_VALUE) {
                        dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
                    } else {
                        dp[i + j] = dp[i] + 1;
                    }
                } else {
                    break;
                }
            }
        }
        // 最后一个位置的状态如果不为 Integer.MAX_VALUE, 就直接返回,
        // 否则说明跳不到该位置, 返回 -1
        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }
}

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n =sc.nextInt();
        int[]nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=sc.nextInt();
        }
        int edge=0,cur=0;
        int cnt=0;
        for(int i=0;i<n;i++){
            if(i>edge){
               System.out.println(-1);
               return;
            }
             edge=Math.max(edge,nums[i]+i);
            if(cur==i&&i!=n-1){
                cnt++;
                cur=edge;
            }
           
        }
       System.out.println(cnt);
    }
}