55. 跳跃游戏

题目链接

动态规划

• 使用reachable数组表示这个点能否到达
• 枚举每个点，若这个点能到达，就从这个点起跳，更新后面的点
• 每次更新的点可以从上一次最后更新的点开始

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        boolean[] reachable = new boolean[len];
        reachable[0] = true;
        int j = 1;
        for(int i = 0; i < len - 1 && j < len; i++){
            if(!reachable[i])continue;
            for(; j < len && j <= i + nums[i]; j++)
                reachable[j] = true;
        }
        return reachable[len-1];
    }
}