Step 0 / 0 · Comparisons: 0 · Swaps: 0
How this algorithm works
How it works
- Allocate one cell per value from 0 up to n.
- Seed the two base cases: fib(0) = 0 and fib(1) = 1.
- Move left to right; each cell is the sum of the two to its left.
- Every cell is computed exactly once and never recomputed.
- The answer sits in the last cell when the table is full.
Key concepts
- Overlapping subproblems — the reason memoisation pays
- Bottom-up tabulation versus top-down memoisation
- Linear time instead of exponential
- Space can drop to O(1) by keeping only the last two values
When to use it
As the first example when learning dynamic programming: the dependency is short enough to hold in your head while the payoff is exponential.
Did you know
fib(78) is the last Fibonacci number a double-precision float holds exactly. Past it the values are merely close.