Dynamic programming is the algorithmic equivalent of "those who cannot remember the past are condemned to repeat it." By caching intermediate results, DP transforms exponential-time recursion into polynomial-time solutions. The key skill is recognizing when subproblems overlap and choosing between top-down memoization and bottom-up tabulation.
The Overlapping Subproblems Problem
Consider the naive Fibonacci implementation:
def fib(n: int) -> int:
if n <= 1:
return n
return fib(n - 1) + fib(n - 2) # exponential!
# fib(40) calls fib(0) 63,245,986 times
# fib(50) would take hoursThe recursion tree has height n and branching factor 2, giving O(2^n) calls. But many subproblems repeat — fib(3) is computed multiple times. DP eliminates this redundancy.
Memoization: Top-Down DP
Add a cache to the recursive solution:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# fib(40) → 41 function calls (O(n) time, O(n) space)Memoization is mechanical: wrap any recursive function in a cache. It's the fastest way to convert a correct recursive solution to a correct DP solution.
# General pattern: memoize any recursive function
def memoize(func):
cache = {}
def wrapper(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrapper
@memoize
def knapsack(weights, values, capacity, i=0):
if i == len(weights) or capacity == 0:
return 0
if weights[i] > capacity:
return knapsack(weights, values, capacity, i + 1)
include = values[i] + knapsack(weights, values, capacity - weights[i], i + 1)
exclude = knapsack(weights, values, capacity, i + 1)
return max(include, exclude)Tabulation: Bottom-Up DP
Solve subproblems in order (smallest to largest), storing results in a table:
def knapsack_tabulation(weights, values, capacity):
"""Bottom-up DP: O(n × capacity) time, O(n × capacity) space."""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w] # don't take item i
if weights[i-1] <= w:
take = dp[i-1][w - weights[i-1]] + values[i-1]
dp[i][w] = max(dp[i][w], take)
return dp[n][capacity]Space Optimization
Many DP problems only need the previous row (or a few previous values):
def knapsack_optimized(weights, values, capacity):
"""Space-optimized: O(capacity) space instead of O(n × capacity)."""
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# Traverse backwards to avoid using updated values
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# 1D array replaces 2D table — same result, O(capacity) spacedef fibonacci_optimized(n: int) -> int:
"""Fibonacci in O(1) space."""
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# O(n) time, O(1) space — optimalThe DP Process: From Recursion to Optimal
# Step 1: Write recursive solution
def coin_change_recursive(coins, amount):
if amount == 0:
return 0
if amount < 0:
return float('inf')
return 1 + min(coin_change_recursive(coins, amount - c) for c in coins)
# Step 2: Add memoization
def coin_change_memo(coins, amount, memo={}):
if amount == 0:
return 0
if amount < 0:
return float('inf')
if amount in memo:
return memo[amount]
memo[amount] = 1 + min(coin_change_memo(coins, amount - c) for c in coins)
return memo[amount]
# Step 3: Convert to tabulation
def coin_change_tabulation(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if a - c >= 0:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1tradeoff / Memoization vs Tabulation
Start with memoization to verify correctness. Convert to tabulation for performance. Apply space optimization when the recurrence only depends on a constant number of previous states.
Memoization is better for sparse subproblem graphs where many entries are never accessed. Tabulation is better for dense problems where you need most entries, and when space optimization is possible.
Synthesis
Dynamic programming transforms exponential recursion into polynomial tabulation by caching overlapping subproblems. Memoization is the easy conversion; tabulation is the fast solution. Space optimization reduces memory usage by exploiting the recurrence structure. Master this progression: recursive → memoized → tabulated → space-optimized.