跳跃游戏2

【链接】https://nanti.jisuanke.com/t/20
【题目】
给定一个非负整数数组，假定你的初始位置为数组第一个下标。

数组中的每个元素代表你在那个位置能够跳跃的最大长度。

你的目标是到达最后一个下标，并且使用最少的跳跃次数。

例如：

A = [2,3,1,1,4]A=[2,3,1,1,4]，到达最后一个下标的最少跳跃次数为 2。（先跳跃 1 步，从下标 0 到 1，然后跳跃 3 步，到达最后一个下标。一共两次）

输入格式

第一行输入一个正整数 n(1 \le n \le 100)n(1≤n≤100) ，接下来的一行，输入 n 个整数，表示数组 A。

输出格式

最后输出最少的跳跃次数。

样例输入

5
3 1 1 1 1
样例输出

2
【代码实现】

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int [] a = new int[n];
        int [] dp = new int[n];
        for (int i = 0;i<n;i++) {
            a[i] = input.nextInt();
            dp[i] = 10000;
        }
        dp[0] = 0;
        for (int i = 0;i<n;i++) {
            for (int j = 1;j<=a[i]&&i+j<n;j++) {
                dp[i+j] = Math.min(dp[i+j], dp[i]+1);
            }
        }
        
        System.out.println(dp[n-1]);
    }
    
}