0055. Jump Game

class Solution {
    // public boolean canJump(int[] nums) {
    //     int n = nums.length;
    //     boolean[] dp = new boolean[n];
    //     Arrays.fill(dp, false);
    //     dp[0] = true;
    //     for (int i = 0; i < n; i++) {
    //         if (dp[i] == false) {
    //             continue;
    //         }
    //         int step = nums[i];
    //         for (int j = 0; i + j < n && j <= step; j++) {
    //             dp[i + j] = true;
    //         }
    //     }
    //     return dp[n - 1];
    // }

    public boolean canJump(int[] nums) {
        int end = 0, max = 0, n = nums.length;
        if (n == 1) {
            return true;
        }
        for (int i = 0; i < n - 1; i++) {
            if (i > max) {
                return false;
            }
            end = i + nums[i];
            max = Math.max(max, end);
            if (max >= n - 1) {
                return true;
            }
        }
        return false;
    }
}