Writing answers on your hand
Memoisation vs Tabulation
The analogy
Computing fib(50) naively recomputes fib(10) millions of times. Write each answer down the first time you work it out and the whole thing collapses to instant. Then notice you could also just fill the answers in order from the bottom, no recursion at all.
Visualizer
The call tree collapses
step 1 / 9The call tree for a naive fib(5). Each node calls two more.fib(5) naive: exponential calls
from functools import cache
@cache # memoisation, top-down
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
def fib_tab(n): # tabulation, bottom-up
dp = [0, 1] + [0] * (n - 1)
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
def fib_opt(n): # O(1) space
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
# state: dp[i] = the i-th Fibonacci number
# transition: dp[i] = dp[i-1] + dp[i-2]
# complexity = states * transition cost = n * O(1)Check yourself
What two properties must a problem have for DP to apply?