Fibonacci Sequence (DP)
Software Engineer path · lesson 34 of 99A classic example of Dynamic Programming. We calculate the Nth number by summing the two preceding ones, storing results in a table (Bottom-Up) to avoid redundant calculations.
Same answer, very different work: compare the call counter.
Recursion with a memo for fib(6).
- 1fib(n):
- 2 if n < 2: return n
- 3 if n in memo: return memo[n] # reuse
- 4 memo[n] = fib(n-1) + fib(n-2)
- 5 return memo[n]
- Function calls
- 0 / 11
- Additions
- 0 / 5
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Three ways to compute fib(n)
Sort each trait into the approach it describes.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
Naive recursion
Drop items hereMemoization (top-down)
Drop items hereTabulation (bottom-up)
Drop items hereTest your knowledge
Why is DP faster than simple recursion for Fibonacci?
The short version
Think of climbing a staircase. To step onto step N, you must have come from either step N-1 or step N-2. The number of ways to reach the top is the sum of the ways to reach the previous two steps.
In more depth
Remembering the Past
Fibonacci is the classic introduction to Dynamic Programming (DP). The core idea is simple: don't solve the same problem twice.
Memoization (Top-Down):
Write a recursive function, but before doing any work, check if you've already solved this input. If yes, return the saved answer.
Tabulation (Bottom-Up):
Start from the smallest cases (0 and 1) and build up the answer for 2, 3, 4... until you reach N. This typically uses iteration and saves stack space.
When to reach for this
- Count the number of ways to reach a state
- Problem can be broken down into overlapping subproblems
- Value at step i depends on previous steps (i-1, i-2)
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required