Tribonnaci implementation using memoization: Runntime error

Question

Hi guys I was trying to implement a solution to tribonaci in java many of you are probably familiar with this leetcode task inside the dynamic programic mini course. Basicly inside the tribonaci t0 = 0 t1 = t2 = 1 and tn = t(n - 3) + t(n-2) + t(n-1). I was trying to implement it via a recursive solution using a hasmap and memoization(going from the top down). However when I am running the code I get a runtime error. Anyone can help me pinpoint the source? Thank you in advance

class Solution {
private HashMap<Integer,Integer> memo = new HashMap<Integer,Integer>();
private int n;
private int dp(int i){
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    if(!memo.containsKey(i)){
        memo.put(i,dp(i - 1) + dp(i - 2) + dp(i - 3));
    }
    return memo.get(i);
}
public int tribonacci(int n) {
    this.n = n;
    return dp(n);
}

}

Answer 1

The problem is that you do not reach the end/bottom of your recursion. You wrote it, tribonacci is - tn = t(n - 3) + t(n-2) + t(n-1), but in you code you do the opposite - dp(n) + dp(n + 1) + dp(n + 2), instead of summing 3 previous values, you sum current value and 2 next. Imagine it like this - you need to go backwards to get already calculated values, but in your code you go forward to the next values, but they do not exist. This is what leads to no bottom of recursion and consecutively to stackoverflowerror.

Here is the code, fixed and somewhat simplified.

public class Tribonnaci {

  private final HashMap<Integer,Integer> memo;

  public Tribonnaci() {
    this.memo = this.initMap();
  }

  private HashMap<Integer, Integer> initMap() {
    //init map, this will be bottom of your recursion
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, 0);
    map.put(1, 1);
    map.put(2, 1);
    //also, cleaner, your bottom is the memoized values
    //not combination of it and if checks
    return map;
  }

  private int calculateNthTribonacci(int n){
    Integer result = this.memo.get(n);
    //if result is null, that means it has not been calculated before
    if (result == null) {
      //sum the three previous values from tribonnaci sequence
      result = this.calculateNthTribonacci(n - 1) + this.calculateNthTribonacci(n - 2) + this.calculateNthTribonacci(n - 3);
      //save it in memo
      this.memo.put(n, result);
    }
    return result;
  }

  public int tribonacci(int n) {
    return calculateNthTribonacci(n);
  }
}

EDIT: Ok, now the problem is instance variable private int n;. You don't use instance variables to check recursion bottom

if (n == 0) return 0;
if (n == 1 || n == 2) return 1;

You have to check the method parameter when bottom is reached. Recursion is calling the same method, inside that method, but giving it different parameter. In your case, this is i:

private int dp(int i)

That's why you need to check value of i for reaching bottom of recursion and get rid of instance variable n. Like this:

public class Tribonnaci {

    private HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();

    private int dp(int i) {
        if (i == 0) return 0;
        if (i == 1 || i == 2) return 1;
        if (!memo.containsKey(i)) {
            int prev = dp(i - 1);
            int prevPrev = dp(i - 2);
            int prevPrevPrev = dp(i - 3);
            int value = prev + prevPrev + prevPrevPrev;
            memo.put(i, value);
        }
        return memo.get(i);
    }

    public int tribonacci(int n) {
        return dp(n);
    }
}

I wrote it verbose on purpose, debug it few times to understand better how recursion works.