lc-55

//You are given an integer array nums. You are initially positioned at the array
//'s first index, and each element in the array represents your maximum jump lengt
//h at that position. 
//
// Return true if you can reach the last index, or false otherwise. 
//
// 
// Example 1: 
//
// 
//Input: nums = [2,3,1,1,4]
//Output: true
//Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
// 
//
// Example 2: 
//
// 
//Input: nums = [3,2,1,0,4]
//Output: false
//Explanation: You will always arrive at index 3 no matter what. Its maximum jum
//p length is 0, which makes it impossible to reach the last index.
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 104 
// 0 <= nums[i] <= 105 
// 
// Related Topics Array Dynamic Programming Greedy 
// 👍 12064 👎 656


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null) {
            return false;
        }

        if (nums.length == 0) {
            return true;
        }

        int[] maxJump = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            maxJump[i] = i + nums[i];
        }

        Boolean[] canJumpBool = new Boolean[nums.length];

        return canJumpInner(maxJump, canJumpBool, nums.length - 1);
    }


    private boolean canJumpInner(int[] maxJump, Boolean[] canJumpBool, int index) {
        if (canJumpBool[index] != null) {
            return canJumpBool[index];
        }

        if (index == 0) {
            canJumpBool[index] = true;
            return true;
        }

        for (int i = 0; i < index; i++) {
            if (maxJump[i] >= index && canJumpInner(maxJump, canJumpBool, i)) {
                canJumpBool[index] = true;
                return true;
            }
        }

        canJumpBool[index] = false;
        return false;
    }


}
//leetcode submit region end(Prohibit modification and deletion)