Find Nth Tribonacci number (Memoization)

Given a positive integer n, find the nth Tribonacci number. Tribonacci numbers, when it starts from 0, are calculaed as T(n), where T(1) = T(2) = 0, T(3) = 1, and T(n) = T(n-1) + T(n-2) + T(n-3) for n > 3. Example of first few Tribonacci numbers are 0, 0, 1, 1, 2, 4, 7, 13, 24, 44.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Tribonacci number, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

Initialize cache to store results.
Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
Return the cached result.

Python
Javascript

# Python implementation

cache = {}

def tri(n):
  if n < 3:
    return 0

  if n == 3:
    return 1

  if n in cache:
    cache[n] = tri(n - 1) + tri(n - 2) + tri(n - 3)

  return cache[n]

n = 10

print(tri(n))

// Javascript implementation

const cache = {}

function tri(n) {
  if (n < 3) {
    return 0;
  }

  if (n == 3) {
    return 1;
  }

  if (cache[n] === undefined) {
    cache[n] = tri(n - 1) + tri(n - 2) + tri(n - 3);
  } 

  return cache[n];
}

const n = 10;

console.log(tri(n));