#1137 - N-th Tribonacci Number

EasyDP - 1D

The Tribonacci sequence: T₀ = 0, T₁ = 1, T₂ = 1, and Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃ for n >= 3. Given n, return Tₙ.

Input	Output
n = 4	4
n = 25	1389537
n = 0	0

Solution Space

Try it

/**
 * Returns the n-th Tribonacci number.
 *
 * @param n Index in the Tribonacci sequence (0 ≤ n ≤ 37)
 * @returns T(n)
 */
export function tribonacci(n: number): number {
  if (n === 0) return 0;
  if (n <= 2) return 1;

  let a = 0,
    b = 1,
    c = 1;

  for (let i = 3; i <= n; i++) {
    const next = a + b + c;
    a = b;
    b = c;
    c = next;
  }

  return c;
}

Approach: iterative with three variables – roll forward, keeping only the last three values.

Time: O(n) – single loop from 3 to n.

Space: O(1) – three numeric variables.

#746 Min Cost Climbing Stairs

#62 Unique Paths