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

1.简述：

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置，则输出true，否则输出false。

数据范围:

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

第二行输入 n 个整数表示数组的每个元素

输出 true 或者 false

输入：

7
2 1 3 3 0 0 100

输出：

true

说明：

首先位于nums[0]=2，然后可以跳2步，到nums[2]=3的位置，再跳到nums[3]=3的位置，再直接跳到nums[6]=100，可以跳到最后，输出true

输入：

7
2 1 3 2 0 0 100

输出：

false

说明：

无论怎么样，都跳不到nums[6]=100的位置

2.代码实现：

import java.util.Scanner;
 
public class Main{
     
    public static void main(String[] args){
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            if (dp[i]) {
                for (int j = i + 1; (j <= i + a[i]) && j < n; j++) {
                    dp[j] = true;
                }
            } else {
                break;
            }
        }
        System.out.println(dp[n - 1]);
        
    }
    
}