N-th Tribonacci Number

Intuition

Because T(n) depends only on the three preceding terms, a naive recursion recomputes the same subproblems an exponential number of times. Storing each result the first time it is produced removes that duplication, so the recursion effectively fills a table from the small indices up to n while each value is computed just once.

Algorithm walkthrough

1. 1Answer the base cases directly: 0 for index 0, and 1 for indices 1 and 2.
2. 2Keep a cache keyed by the index, initialized to a sentinel meaning 'not computed yet'.
3. 3When asked for T(k), return the cached value if it exists.
4. 4Otherwise compute T(k-1) + T(k-2) + T(k-3), store it, and return it.

Implementation

class Solution:
    def tribonacci(self, n: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        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)

Intuition

Only the three most recent values are ever needed to produce the next one, so there is no reason to keep the whole table around. Three rolling variables advance one index at a time, which keeps memory constant while still following the same recurrence.

Algorithm walkthrough

1. 1Return early for the base indices 0, 1, and 2.
2. 2Initialize three variables a, b, c to T(0), T(1), T(2) = 0, 1, 1.
3. 3For each index from 3 up to n, compute next = a + b + c.
4. 4Slide the window forward: a becomes b, b becomes c, c becomes next.
5. 5After the loop c holds T(n).

Implementation

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