Jump Game - Leetcode

canJump.java

/*
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.

Algorithm:
1. Recursivly find the solution by increasing 1 step. Since it is
slow, and it only pass the small test case.

Impoved this algorithm with caching, using a hash table with keys of 
cur(position) and maxJump(how much can it jump)

*/
public class Solution {
    public boolean canJump(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A.length == 0 || A.length == 1) return true;
        return canJumpHelper(A, 0, A[0], A.length - 1);
    }
    
    public boolean canJumpHelper(int[] A, int cur, int maxJump, int target) {
        if(cur > target) return false;
        
        for(int i = 1; i <= maxJump; i++) {
            if(i+cur == target) return true;
            if(canJumpHelper(A, i+cur, A[i+cur], target)) return true;
        }
        
        return false;
    }
}