Fibonacci
f(n) = f(n-1) + f(n-2); the smallest example of memoization versus tabulation.
Decision · step 2 of 11DP in One Row: Fibonacci by table
dp[2] = dp[1] + dp[0] = 1 + 0 = 1.
What you will see
Naive tree explodes; memoized tree collapses; table fills left to right.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(1) |
O(2^n) naive; O(n) memoized; O(1) space with two variables.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
Taught by the same lesson
DP in One Row covers these too, in the same run.