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

Building upon understanding of Tribonacci number (Memoization). Pay attention to the cache. Tabulation essentially reconstructs the cache.

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

# Python implementation

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

  if n == 3:
    return 1

  result = 0
  prev_1 = 1
  prev_2 = 0
  prev_3 = 0

  for i in range(4, n + 1):
    result = prev_1 + prev_2 + prev_3
    prev_3 = prev_2
    prev_2 = prev_1
    prev_1 = result
  
  return result

n = 10

print(tri(n))

// Javascript implementation

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

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

  let result = 0;
  let prev_1 = 1;
  let prev_2 = 0;
  let prev_3 = 0;

  for (let i = 4; i <= n; i++) {
    result = prev_1 + prev_2 + prev_3;
    prev_3 = prev_2;
    prev_2 = prev_1;
    prev_1 = result;
  }
  
  return result;
}

const n = 10;

console.log(tri(n));

Find Nth Tribonacci number (Tabulation)

Hint