Pattern visualizer
N-th Tribonacci Number
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. 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..
Bottom-up constant-space 3-variable DP
time O(n)space O(1)step 1 / 8
0
[0]1
[1]1
[2]0
[3]0
[4]line 4
Initialize dp table of size 5 for n=4. Seed base values: dp[0]=0, dp[1]=1, dp[2]=1.
Pseudocode
1FUNCTION tribonacci(n):2 IF n is 0: RETURN 03 IF n is 2 or less: RETURN 14 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