Memoization gives StackOverflowError, use Tabulation/Bottom-up approach


#1

public class Solution {
public static boolean[] dp;

public int canJump(ArrayList<Integer> A) {
    int n = A.size();
    dp = new boolean[n + 1];
    
    dp[n] = true;
    
    for (int i = n - 1; i >= 1; i--) {
        for (int jmp = 1; jmp <= A.get(i - 1); jmp++) {
            dp[i] = dp[i + jmp] || dp[i];
            
            if (dp[i])
                break;
        }
    }

    return dp[1] ? 1 : 0;
}

}