Jump game leetcode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

state: f[i]表示能否从起点跳到i点

function： f[i] = 是否能从前面任意j点跳到i点

initial： f[0] = true

final : return f[n-1]

  时间O(n^2) 空间O(n)

public class Solution {
    
    public boolean canJump(int[] A) {
        boolean [] can = new boolean [A.length];// 每次都要创建长度为length的数组
        can[0] = true;
        for (int i = 1; i < A.length; i++) {//i的起始点应该为1
            for (int j = 0; j < i; j++) {
                if (can[j] && j + A[j] >= i) {
                    can[i] = true;
                    break;
                }
            }
        }
        return can[A.length - 1];
    }
}

贪心:
起始便利啊范围是0 ~ nums[0] 随着便利进行 范围会变为max的值  但是要小于nums长度
在位置i可以跳的最远距离为nums[i] + i , 维护一个max 记录能跳的最远距离
每次跳完更新max = max(max, num[i] + i)
时间是O(n) 空间O(1)

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