Accepted on Leetcode , Stack overflow on IB (Top down approach + recursion)


#1

Again one more scenario where using top down approach with recursion is giving stack overflow but it gets passed in leetcode .

public class Solution {
public int canJump(ArrayList A) {

    int[] dp = new int[A.size()];
for (int i =0; i < A.size(); i++)
  dp[i] = -1;

boolean canJump = canJump(dp, A, 0, A.size()-1);
if(canJump)
  return 1;
return 0;
}

private boolean canJump(int[] dp , ArrayList<Integer> A, int low , int high){
if(low >= high)
  return true;

if(dp[low] != -1){
  if(dp[low] == 0){
    return false;
  }
  if(dp[low] == 1){
    return true;
  }
}

int jumpCount = A.get(low);
for (int i =1 ; i <= jumpCount; i++){
  boolean canReach = canJump(dp, A, low+i, high);
  if(canReach){
    dp[low] = 1;
    return true;
  }
}

dp[low] = 0;
return false;

}
}