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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 标准输入
        Scanner input = new Scanner(System.in);
        // 获取数组长度
        int len = input.nextInt();
        // 获取输入数组
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = input.nextInt();
        }
        // 调用动态规划函数
        boolean res = dp(nums);
        // 输出结果
        System.out.println(res);
    }

    // 动态规划函数
    private static boolean dp(int[] nums) {
        // 预处理
        if (nums.length == 1) return true;
        // 初始化
        int len = nums.length;
        int furthest = 0;
        // 遍历数组，动态更新最远距离
        for (int i = 0; i < len-1; i++) {
            if (i <= furthest) { // 尚未越界
                // 状态转移
                furthest = Math.max(furthest, i + nums[i]);
                if (furthest >= len-1) { // 能到达数组最后一位
                    return true;
                }
            }
        }
        // 遍历结束尚未返回，则不能到达数组末
        return false;
    }
}