Tribonacci Numbers
Return the nth Tribonacci number, where the sequence starts 0, 1, 1 and each later term is the sum of the three terms directly before it. State the value for a given index without listing the whole sequence up to it.
Do this lesson first: climbing stairsExample input
n = 8
Expected output
44
Break it down
Answer each question out loud before you open it. Getting it wrong here is the useful part — a revealed answer you never guessed at teaches you nothing.
Fill the table
The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.
Press start. The animation stops at every cell YOUR recurrence must fill.
dp[0] = 0, dp[1] = 1, and dp[2] = 1 are given by definition; a third base case is needed because the recurrence now reaches three cells back. Every other cell depends only on smaller indices, so filling left to right still guarantees all three dependencies exist before they are read.
- 1
function trib(n) { - 2
const dp = [0, 1, 1]; - 3
for (let i = 3; i <= n; i++) { - 4
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; - 5
} - 6
return dp[n]; - 7
}
The code, the trap, the variations
- 1
function trib(n) { - 2
const dp = [0, 1, 1]; - 3
for (let i = 3; i <= n; i++) { - 4
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; - 5
} - 6
return dp[n]; - 7
}
Where people go wrong
The third base case. Some sources start Tribonacci 0, 0, 1 rather than 0, 1, 1, which shifts every later term. Pin down all three seed values from the problem statement before writing the loop — one wrong seed silently poisons the whole table.
Sum the two before it instead of the three.
That is Fibonacci — one fewer bucket, one fewer base case, same left-to-right order.
Sum the four before it instead of the three.
A fourth bucket and a fourth base case, nothing else. The state, the order, and the fact that every term is a plain sum all stay the same — only how many neighbors combine grows.