Fibonacci Numbers
Return the nth Fibonacci number, where the sequence starts 0, 1 and each later term is the sum of the two before it. Naive recursion recomputes the same terms exponentially many times.
Do this lesson first: climbing stairsExample input
n = 7
Expected output
13
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 and dp[1] = 1 are given by definition; they cannot be derived. Every other cell depends only on smaller indices, so filling left to right guarantees both dependencies exist before they are read.
- 1
function fib(n) { - 2
const dp = [0, 1]; - 3
for (let i = 2; i <= n; i++) { - 4
dp[i] = dp[i - 1] + dp[i - 2]; - 5
} - 6
return dp[n]; - 7
}
The code, the trap, the variations
- 1
function fib(n) { - 2
const dp = [0, 1]; - 3
for (let i = 2; i <= n; i++) { - 4
dp[i] = dp[i - 1] + dp[i - 2]; - 5
} - 6
return dp[n]; - 7
}
Where people go wrong
Indexing off by one. Plenty of sources start the sequence 1, 1 rather than 0, 1, so dp[7] is 13 under one convention and 21 under the other. Fix the two base cases first and state them out loud before writing the loop.
Sum the two before it, but return the result modulo 1e9+7.
The recurrence does not change at all. Only the combine step gains a modulo, which is why huge-n versions of this problem are still one line different.
Sum the three before it instead of the two.
Three buckets instead of two, and a third base case. That is exactly Tribonacci — the state and the order are untouched.