Given a number n, calculate the corresponding Tribonacci number.

tribonacci.js

export function findTribonacci(n) {
  // we use an array of fixed size so we keep a constant amount of subproblem solutions at each iteration
  // therefore ensuring constant space complexity
  const dp = [0, 1, 1];

  if (n < 3) {
    return dp[n];
  }

  for (let i = 3; i <= n; ++i) {
    const result = dp[0] + dp[1] + dp[2];
    dp[0] = dp[1];
    dp[1] = dp[2];
    dp[2] = result;
  }

  return dp[2];
}

// tc: O(n)
// sc: O(1)