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 aIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.