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

1.簡述：

描述

給定一個非負整數數組nums，假定最開始處于下标為0的位置，數組裡面的每個元素代表下一跳能夠跳躍的最大長度。如果能夠跳到數組最後一個位置，則輸出true，否則輸出false。

資料範圍:

輸入描述：

第一行輸入一個正整數 n ，表示數組 nums 的長度

第二行輸入 n 個整數表示數組的每個元素

輸出描述：

輸出 true 或者 false

示例1

輸入：

7
2 1 3 3 0 0 100      

輸出：

true      

說明：

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

示例2

輸入：

7
2 1 3 2 0 0 100      

輸出：

false      

無論怎麼樣，都跳不到nums[6]=100的位置      

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