N-th Tribonacci Number

Problem in plain words

The Tribonacci sequence starts with 0, 1, 1, and every later term is the sum of the three terms just before it. Given n (at most 37), return term number n, counting from 0.

So the sequence goes 0, 1, 1, 2, 4, 7, 13, 24, and the answer for n = 6 is 13.

Intuition

This is Fibonacci with one more term in the sum. A naive recursion recomputes the same terms an exponential number of times, but each term only depends on the three before it, so we can build the sequence from the bottom up and keep only a sliding window of three values. The same idea is animated in the bottom-up Fibonacci DP lesson.

Approach

1. State: T(i) is the i-th Tribonacci number.
2. Recurrence: T(i) = T(i - 1) + T(i - 2) + T(i - 3).
3. Base cases: T(0) = 0, T(1) = 1, T(2) = 1. Return them directly when n < 3.
4. Order: compute from i = 3 up to n, holding the last three values in a, b, c and shifting them after each step.

Dry run

Input: n = 5. Start with a = 0, b = 1, c = 1.

The answer is c = 7.

Java solution

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n < 3) return 1;
        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }
        return c;
    }
}

Python solution

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

Complexity

Edge cases and common mistakes

• n = 0, 1, 2: handle these before the loop; returning c for n = 0 would wrongly give 1.
• Overflow: the constraint n <= 37 keeps the answer under 2^31, so int is safe. For larger n you would need long or a modulus.
• Plain recursion: T(n-1) + T(n-2) + T(n-3) without memoization is roughly O(1.84^n) and times out well before n = 37 in some languages.
• Shifting in the wrong order: in Java, compute next first, then shift a, b, c; overwriting c first loses a value.