Top-Down vs Bottom-Up
Dynamic Programming: lesson 2 of 10
One recurrence, two directions: recurse and cache, or fill a table.
Lesson 2 of 10 · 5 min
Top-Down vs Bottom-Up
Step 1 of 12
Top-down starts at the full problem — fib(4) — and recurses only into what it actually needs.
The Idea
Two directions, one recurrence. Top-down starts at the full problem, recurses, and caches whatever it meets — so it touches only the subproblems it actually needs. Bottom-up starts at the base cases and fills a table forward, so every dependency is ready before it is read. Top-down is easier to derive from the recursion; bottom-up avoids deep call stacks.
Real-World Example
Revising for an exam. Top-down means opening the hardest past paper and looking things up only when a question demands them. Bottom-up means working the syllabus chapter by chapter, so nothing is ever missing when you reach the paper — though you also study pages the paper never asks about.
The Code
def top_down(n, memo):
if n < 2:
return n
if n not in memo: # solve on demand
memo[n] = top_down(n - 1, memo) + top_down(n - 2, memo)
return memo[n]
def bottom_up(n):
table = [0, 1] + [0] * (n - 1) # base cases first
for i in range(2, n + 1): # dependency order
table[i] = table[i - 1] + table[i - 2]
return table[n]
print(top_down(30, {}), bottom_up(30)) # 832040 832040Your turn
Put the steps in the right order.
- Fill the remaining cells in dependency order
- Decide what a single table cell will mean
- Read the final cell as the answer
- Write the base-case cells in directly
Mini quiz
1 / 3