Jump Game

Leetcode https://leetcode.cn/problems/jump-game/

class Solution {
    public boolean canJump(int[] nums) {

        if (nums == null || nums.length == 0) {
            return false;
        }

        int n = nums.length;
        boolean[] canHop = new boolean[n];
        canHop[n-1] = true;
        
        for (int i = n - 2; i >= 0; i--) {
            if (i + nums[i] >= n - 1) {
                canHop[i] = true;
            } else {
                for (int j = 1; j <= nums[i]; j++) {
                    if (canHop[i + j]) {
                        canHop[i] = true;
                        break;
                    }
                }
            }
        }

        return canHop[0];
    }
}

Complexity

• Time = O(n^2)
• Space = O(n)

---