N-th Tribonacci Number

Problem

The Tribonacci sequence is defined by:

• T(0) = 0, T(1) = 1, T(2) = 1
• T(k) = T(k-1) + T(k-2) + T(k-3) for k >= 3

Given an integer n, return T(n).

Examples

• n = 4 → 4 — the sequence starts 0, 1, 1, 2, 4; T(3) = 0+1+1 = 2, T(4) = 1+1+2 = 4.
• n = 25 → 1389537.
• n = 0 → 0 — the very first term.

Constraints

• 0 <= n <= 37
• The answer fits in a signed 32-bit integer.

Like Fibonacci, the small bound means any linear method is fast enough. The pitfall is naive recursion, which re-expands three branches per call and runs in exponential time.

Think about it first

TL;DR

Slide a 3-wide window of previous terms forward: O(n) time, O(1) space.

The recurrence

T(k) = T(k-1) + T(k-2) + T(k-3)   for k >= 3
T(0) = 0,  T(1) = 1,  T(2) = 1

Approach 1 — Brute-force recursion

Transcribe the recurrence; each call fans out into three.

def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    if n <= 2:
        return 1
    return (tribonacci(n - 1)
            + tribonacci(n - 2)
            + tribonacci(n - 3))

Complexity: ~O(3^n) time, O(n) stack.

At n = 37 the three-way branching re-derives the same lower terms billions of times. The recursion tree below shows the repeated work: T(2) alone appears many times even for a small n.

flowchart TD
    A["T(4)"] --> B["T(3)"]
    A --> C["T(2)"]
    A --> D["T(1)"]
    B --> E["T(2)"]
    B --> F["T(1)"]
    B --> G["T(0)"]

Each T(k) recomputes its entire subtree from scratch. The next three approaches remove that duplication.

Approach 2 — Top-down memoization

There are only n + 1 distinct terms. Cache each so it is computed once.

from functools import cache

def tribonacci(n: int) -> int:
    @cache
    def T(k: int) -> int:
        if k == 0:
            return 0
        if k <= 2:
            return 1
        return T(k - 1) + T(k - 2) + T(k - 3)
    return T(n)

Complexity: O(n) time, O(n) space (cache + stack).

Approach 3 — Bottom-up tabulation

Compute T(0), T(1), … , T(n) in order so each term’s three predecessors are already stored.

def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    if n <= 2:
        return 1
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    for k in range(3, n + 1):
        dp[k] = dp[k - 1] + dp[k - 2] + dp[k - 3]
    return dp[n]

Walkthrough (n = 4): dp = [0, 1, 1, ?, ?]. dp[3] = 1+1+0 = 2, dp[4] = 2+1+1 = 4. Return 4.

Complexity: O(n) time, O(n) space.

Approach 4 — Space-optimized (rolling triple)

T(k) reads only the previous three terms, so three variables replace the whole table.

def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    if n <= 2:
        return 1
    a, b, c = 0, 1, 1                 # T(0), T(1), T(2)
    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c
    return c

Walkthrough (n = 25): starting (a,b,c) = (0,1,1), each step drops the oldest term and appends the new sum. After 23 iterations c = 1389537.

Complexity: O(n) time, O(1) space.

Common pitfalls

• Wrong base cases. Note T(2) = 1, not 2. A wrong seed (e.g. treating it like Fibonacci with only two bases) shifts the whole sequence.
• Not short-circuiting n < 3. The rolling-triple loop assumes at least the three seeds exist; return the base values directly for n = 0, 1, 2.
• Sliding the window in the wrong order. Use simultaneous assignment a, b, c = b, c, a+b+c; updating a before computing the sum corrupts it.

Pattern takeaway

Tribonacci generalizes the Fibonacci DP from a 2-wide to a 3-wide look-back window: the same recurrence structure, with one more term in the sum. The reusable rule: when a recurrence depends on a fixed number w of previous states, tabulate bottom-up, then keep only the last w values as rolling variables for O(1) space.