N-th Tribonacci Number: Dynamic Programming Fundamentals

The Tribonacci sequence is defined as: T(0) = 0, T(1) = 1, T(2) = 1, and for all n >= 3, T(n) = T(n-1) + T(n-2) + T(n-3). Given n, return the value of T(n).

This is LeetCode 1137: N-th Tribonacci Number, and it is one of the cleanest problems for learning the rolling window optimization in dynamic programming. If you have already solved Fibonacci Number, this problem extends that same idea from two lookback variables to three.

Why this problem matters

The Tribonacci problem looks like a small variation of Fibonacci, and it is. But that small variation teaches something important: the constant-state DP pattern generalizes to any fixed lookback window. Fibonacci uses two variables. Tribonacci uses three. Once you see how the pattern scales, you can handle any recurrence where dp[i] depends on a fixed number of previous values.

This is the same building block behind Climbing Stairs, House Robber, and Decode Ways. The number of variables changes, but the structure stays identical: initialize your base cases, loop forward, slide the window, and return the result.

The approach

A naive recursive solution would call tribonacci(n-1), tribonacci(n-2), and tribonacci(n-3) at every level. That creates an exponential blowup similar to recursive Fibonacci, but even worse since each call branches into three instead of two.

The fix is bottom-up dynamic programming with space optimization. You do not need an array at all. Since T(n) only depends on the three values immediately before it, three variables are enough:

1. Initialize a = 0, b = 1, c = 1 for T(0), T(1), T(2).
2. For each step from 3 to n, compute the sum a + b + c.
3. Slide the window: a becomes b, b becomes c, c becomes the new sum.
4. After the loop, c holds T(n).

The solution

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

    a, b, c = 0, 1, 1

    for i in range(3, n + 1):
        a, b, c = b, c, a + b + c

    return c

The first two guards handle the base cases directly. T(0) = 0, and both T(1) and T(2) equal 1.

a, b, and c represent the three most recent tribonacci values. They start as T(0) = 0, T(1) = 1, and T(2) = 1.

The loop runs from i = 3 to i = n. At each step, Python's tuple assignment computes the new sum and shifts the window in a single line. a takes the old value of b, b takes the old value of c, and c becomes the sum of all three previous values.

After the loop, c holds T(n).

Step-by-step walkthrough

Let's trace through computing T(3) through T(6). At each step, the yellow cells are the three source values being summed, and the green cell is the newly computed result.

A few things to notice:

• The window of three "active" cells slides forward by one position at each step.
• You never look further back than three positions, which is why three variables replace the entire array.
• The three base cases T(0) = 0, T(1) = 1, and T(2) = 1 anchor the computation. Without them, there is nothing to build from.

Complexity analysis

Time: O(n). You compute each tribonacci value from T(3) to T(n) exactly once. Each computation is a single addition of three values, so the total work is linear.

Space: O(1). You store only three variables (a, b, and c) regardless of how large n is. No array, no recursion stack, no memo dictionary.

The building blocks

1. Base case handling for multi-term recurrences

When a recurrence depends on three previous values, you need three base cases before the loop can start:

if n == 0:
    return 0
if n <= 2:
    return 1

a, b, c = 0, 1, 1

This is the same idea as the two-variable Fibonacci guard (if n < 2: return n), extended by one term. The principle is general: if your recurrence looks back k steps, you need k base cases and k variables. This pattern appears whenever you encounter a higher-order linear recurrence.

2. Rolling window with three variables

The constant-state DP pattern generalized from two variables to three:

for i in range(3, n + 1):
    a, b, c = b, c, a + b + c

For Fibonacci, you slide a window of two variables. For Tribonacci, you slide a window of three. The structure is identical. If you ever encounter a "tetranacci" or any k-step recurrence, you extend the same pattern to k variables. Recognizing this generalization means you can solve the entire family of problems with the same template.

Edge cases

• n = 0: return 0. The zeroth tribonacci number is 0 by definition.
• n = 1: return 1. The sequence has barely started.
• n = 2: return 1. This is the last base case, not yet computed from the recurrence.
• n = 3: return 2. The first "computed" value: T(3) = 1 + 1 + 0 = 2.
• Large n (up to 37): the O(1) space solution handles the LeetCode constraint instantly. No risk of overflow within the constraint bounds.

From understanding to recall

The tribonacci recurrence is simple, and extending Fibonacci from two variables to three feels natural. But the real skill is not remembering the formula T(n) = T(n-1) + T(n-2) + T(n-3). It is recognizing the rolling window pattern instantly and applying it without hesitation when you see a new recurrence in an interview.

Spaced repetition turns that recognition into a reflex. You revisit the three-variable sliding window template at increasing intervals, write it from scratch each time, and after a few reps you stop thinking about which variable gets shifted where. The pattern is just there, ready to deploy whether the problem says "tribonacci," "climbing stairs with three step sizes," or anything else with a fixed lookback window.

Related posts

• Fibonacci Number - The two-variable version of this same pattern, the natural predecessor to Tribonacci
• Climbing Stairs - Same constant-state DP skeleton applied to counting distinct paths up a staircase
• House Robber - Two-variable DP with a max decision at each step, showing how the template adapts to different combination functions

CodeBricks breaks the N-th Tribonacci Number into its base case handling and rolling window building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a DP problem with a fixed lookback window shows up in your interview, you do not think about it. You just write it.