N-th Tribonacci Number

Bottom-up constant-space 3-variable DP

time O(n)space O(1)

Each Tribonacci number depends strictly on the sum of the preceding three numbers in the sequence. Rather than recomputing overlapping subproblems exponentially with naive recursion, dynamic programming builds from the bottom up. Because any step only needs the three most recent values, we can store just T(i-3), T(i-2), and T(i-1) in three variables (or a 1D DP table [T0, T1, T2, T3, T4]), sliding forward one step at a time.

Details

Animated on: Compute T(4) where T(0)=0, T(1)=1, T(2)=1, and T(n) = T(n-1) + T(n-2) + T(n-3) for n >= 3.

Problem:N-th Tribonacci NumberEasy

Bottom-up constant-space 3-variable DP

step 1 / 8

[0]

[1]

[2]

[3]

[4]

Initialize dp table of size 5 for n=4. Seed base values: dp[0]=0, dp[1]=1, dp[2]=1.

dp[0]=0· arr[0] = 0
dp[1]=1· arr[1] = 1
dp[2]=2· arr[2] = 1

Pseudocode

1FUNCTION tribonacci(n):
2  IF n is 0: RETURN 0
3  IF n is 2 or less: RETURN 1
4  dp = [0, 1, 1]   (the base values dp[0], dp[1], dp[2])
5  FOR i from 3 to n:
6    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
7  RETURN dp[n]

← / → step · space play · Home restart

Every step in words

Show all 8 steps

Initialize dp table of size 5 for n=4. Seed base values: dp[0]=0, dp[1]=1, dp[2]=1.
For i=3, look back at the previous 3 terms: dp[0]=0, dp[1]=1, and dp[2]=1.
Compute dp[3] = dp[2] + dp[1] + dp[0] = 1 + 1 + 0 = 2. dp[0]=0 is no longer needed for subsequent terms.
For i=4 (goal), identify the 3 preceding terms: dp[1]=1, dp[2]=1, and dp[3]=2.
Compute dp[4] = dp[3] + dp[2] + dp[1] = 2 + 1 + 1 = 4. Record dp[4] = 4.
Loop reaches n=4. All required subproblems solved in linear time O(n).
Return dp[4] = 4. Sequence: T0=0, T1=1, T2=1, T3=2, T4=4.
Answer: T(4) = 4.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve N-th Tribonacci Number in the editor All Dynamic Programming problems Back to roadmap