LeetCode 1137 · Recursion · DP

N-th Tribonacci Number, explained with a picture

A staircase with 1, 2 or 3-step jumps.

Recursion · DP
▶ Watch it step by step

The problem

Tribonacci: T0 = 0, T1 = 1, T2 = 1, and each next number is the sum of the previous three. Return Tn.

Input:  n = 7
Output: 24

Picture it

Picture a staircase where you can jump 1, 2 or 3 steps. The ways to reach a step = the sum of the ways to reach the three steps below it. Only the last three numbers need to be remembered.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Rolling three variables. O(n), O(1).

Python solution

def tribonacci(n):
    a, b, c = 0, 1, 1
    for _ in range(n):
        a, b, c = b, c, a + b + c
    return a

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.