🌕 55. 跳跃游戏

难度: 🌕

问题描述

---

解法

class Solution {
    public boolean canJump(int[] nums) {
        // 思路：
        // dp[i] - 以 i 为当前位置，能到达的最远距离
        int len = nums.length;
        if(len == 1) {
            return true;
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        if(dp[0] >= len - 1) {
            return true;
        }
        // dp[0] < len - 1
        for(int i = 1; i < len; i ++) {
            if(dp[i - 1] >= i) {
                // 说明 i - 1 处最远到达的距离能够覆盖当前节点
                int curMax = i + nums[i];
                dp[i] = Math.max(dp[i - 1], curMax);
                if(dp[i - 1] >= len - 1) {
                    return true;
                }
            } else {
                return false;
            }
        }
        return false;
    }
}

---

输出