EasyDynamic ProgrammingRecursionMemoizationMath

N-th Tribonacci Number

2 approaches, code in every language

The Tribonacci sequence is seeded with T(0) = 0, T(1) = 1, and T(2) = 1. From there on, every term is the sum of the three that come right before it, so T(n) = T(n - 1) + T(n - 2) + T(n - 3) for any n greater than 2.

Given a non-negative index n, return the value of T(n).

Example 1

Input: n = 4

Output: 4

T(3) = 0 + 1 + 1 = 2, and then T(4) = 1 + 1 + 2 = 4.

Example 2

Input: n = 25

Output: 1389537

Constraints

0 ≤ n ≤ 37
The answer is guaranteed to fit inside a signed 32-bit integer (at most 2^31 − 1).

Top-down recursion with memoization

Recurse on the triple recurrence but cache each T(k) so every index is solved exactly once.

Loading animation…

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

1Answer the base cases directly: 0 for index 0, and 1 for indices 1 and 2.
2Keep a cache keyed by the index, initialized to a sentinel meaning 'not computed yet'.
3When asked for T(k), return the cached value if it exists.
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)

Time

O(n)

Space

O(n)

Bottom-up with rolling variables

Walk the recurrence forward keeping only the last three terms in constant space.

Loading animation…

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

1Return early for the base indices 0, 1, and 2.
2Initialize three variables a, b, c to T(0), T(1), T(2) = 0, 1, 1.
3For each index from 3 up to n, compute next = a + b + c.
4Slide the window forward: a becomes b, b becomes c, c becomes next.
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

Time

O(n)

Space

O(1)

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Three-Day Dispatch Ladder is our own problem on the technique behind N-th Tribonacci Number: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free

N-th Tribonacci Number

Problem description

Example 1

Example 2

Constraints

Create a free account to see the solution

Now solve one you haven't seen.