The same recurrence can run top-down with recursion plus a cache, or bottom-up by filling a table from the small cases up. Both compute the same values at the same cost.
About 3 min of reading
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Solve one recurrence two ways.
Coins for 6 top-down.
Before you run it, say out loud what it will print. Then open the answer.
Coins for 6 bottom-up.
Before you run it, say out loud what it will print. Then open the answer.
Fib 50 rolling.
Before you run it, say out loud what it will print. Then open the answer.
Coins for 4 bottom-up.
Before you run it, say out loud what it will print. Then open the answer.
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
Top-down recurses from the goal down to the base with a cache. Bottom-up starts at the base and fills up. Both are the same set of equations.
When n is large, bottom-up avoids the recursion limit entirely. That is the reason competitive code often prefers it.
from functools import lru_cache
@lru_cache(maxsize=None)
def coins(n):
if n == 0:
return 1
if n < 0:
return 0
return coins(n - 1) + coins(n - 2)
print(coins(6))Recursion plus a cache is top-down. It computes only the states it reaches.
def coins(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
return dp[n]
print(coins(6))Fill the table from zero upward. No recursion and no cache, just a loop.
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
if n < 2:
return n
return f(n - 1) + f(n - 2)
def g(n):
dp = [0] * (max(n, 1) + 1)
dp[0], dp[1] = 0, 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(f(7) == g(7))Top-down and bottom-up agree. The recurrence is the same, the order differs.
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib(50))A rolling table uses constant memory and no stack. Deep n is safe.
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
if n < 2:
return n
return f(n - 1) + f(n - 2)
print(f(10))Top-down computes only needed states. Bottom-up fills every index up to n.
def coins(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
return dp[n]
print(coins(4))Each cell needs smaller cells, so fill left to right. The dependency sets the order.
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib(10))Only the last two values are read, so keep just those. The table shrinks to two cells.
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
if n < 2:
return n
return f(n - 1) + f(n - 2)
print(f(3))Top-down reads like the recurrence and skips unused states. Bottom-up is faster when you need all of them.
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.