题解 | #跳跃游戏(一)#

// 方法一：保存布尔型dp数组表示该格子能否到达
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]);
        
    }
    
}

// 方法二：保存dp记录能到达的最大距离
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();
        }
        int dp = a[0];
        for (int i = 1; i < n && i <= dp; i++) {
            dp = Math.max(dp, a[i] + i);
        }
        System.out.println(dp >= n-1);
        
    }
    
}