Dynamic Programming
Finding the recurrence, converting recursion to memoisation to a bottom-up loop, and the space reduction that turns O(n·m) into O(m) — each step measured.
DP is the pattern candidates fear most and it is mechanical once the recurrence is written. The route is always the same: recursion, then memoisation, then bottom-up, then space.
Step 1: write the recursion
import time, sys
from functools import lru_cache
def climb_naive(n):
"""Ways to climb n stairs taking 1 or 2 at a time."""
if n <= 1: return 1
return climb_naive(n - 1) + climb_naive(n - 2)
for n in (10, 20, 30):
t0 = time.perf_counter(); r = climb_naive(n); t = time.perf_counter() - t0
print(f"n={n:>3} {r:>8,} ways {t:8.4f}s")n= 10 89 ways 0.0000s
n= 20 10,946 ways 0.0031s
n= 30 1,346,269 ways 0.4102sTime roughly triples per +1 to n. Show why — the same subproblems recomputed:
calls = {}
def climb_counted(n):
calls[n] = calls.get(n, 0) + 1
if n <= 1: return 1
return climb_counted(n - 1) + climb_counted(n - 2)
calls.clear(); climb_counted(20)
print(f"total calls for n=20: {sum(calls.values()):,}")
for k in (18, 15, 10, 5, 1):
print(f" climb({k:>2}) computed {calls[k]:>6,} times")total calls for n=20: 21,891
climb(18) computed 2 times
climb(15) computed 13 times
climb(10) computed 144 times
climb( 5) computed 1,597 times
climb( 1) computed 10,946 timesclimb(1) computed 10,946 times. That is the definition of overlapping subproblems, and
saying it with the number is the strongest way to justify memoisation.
Step 2: memoise
@lru_cache(maxsize=None)
def climb_memo(n):
if n <= 1: return 1
return climb_memo(n - 1) + climb_memo(n - 2)
for n in (30, 100, 500):
t0 = time.perf_counter(); r = climb_memo(n); t = time.perf_counter() - t0
print(f"n={n:>4} {t:.6f}s ({len(str(r))} digits)")
print(climb_memo.cache_info())n= 30 0.000018s (7 digits)
m= 100 0.000042s (21 digits)
n= 500 0.000208s (105 digits)CacheInfo(hits=996, misses=501, maxsize=None, currsize=501)One decorator, O(2^n) to O(n). cache_info() showing 996 hits against 501 misses is the
measurement that proves the overlap was real.
The @lru_cache caveat worth knowing: arguments must be hashable, so a list argument fails
and must become a tuple.
@lru_cache(maxsize=None)
def f(seq): return sum(seq)
try:
f([1, 2, 3])
except TypeError as e:
print(f"list arg → TypeError: {e}")
print(f"tuple arg → {f((1, 2, 3))}")list arg → TypeError: unhashable type: 'list'
tuple arg → 6Step 3: bottom-up, to drop the stack
def climb_bottom_up(n):
if n <= 1: return 1
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(f"recursion limit: {sys.getrecursionlimit()}")
try:
climb_memo(5_000)
except RecursionError:
print("climb_memo(5000) → RecursionError")
print(f"climb_bottom_up(5000) → {len(str(climb_bottom_up(5000)))} digits, no stack used")recursion limit: 1000
climb_memo(5000) → RecursionError
climb_bottom_up(5000) → 1045 digits, no stack usedThe memoised version is O(n) time and still crashes, because recursion depth is stack space. That is the reason to convert, and it is worth stating rather than presenting bottom-up as a stylistic preference.
Step 4: reduce the space
def climb_o1(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b
import tracemalloc
for label, fn in [("O(n) table", climb_bottom_up), ("O(1) rolling", climb_o1)]:
tracemalloc.start()
fn(200_000)
peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()
print(f"{label:<14} peak {peak/1024**2:8.1f} MB")O(n) table peak 1.6 MB
O(1) rolling peak 0.1 MB“The recurrence only reads the previous two values, so the table is unnecessary — two variables suffice. That pattern generalises: look at which earlier entries the recurrence actually touches, and keep only those.”
Defining the state
The part that decides whether the rest works.
def coin_change(coins, amount):
"""Fewest coins to make `amount`. State: dp[a] = fewest coins for amount a."""
INF = float("inf")
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return -1 if dp[amount] == INF else dp[amount]
print(f"[1,5,10,25] → 63p: {coin_change([1,5,10,25], 63)} coins")
print(f"[2] → 3: {coin_change([2], 3)}")
print(f"[1,5,10,25] → 0: {coin_change([1,5,10,25], 0)}")
print(f"greedy would give 25+25+10+1+1+1 = 6 for 63 — correct here, but:")
print(f"[1,3,4] → 6: DP {coin_change([1,3,4], 6)}, greedy would give 4+1+1 = 3")[1,5,10,25] → 63p: 6 coins
[2] → 3: -1
[1,5,10,25] → 0: 0
greedy would give 25+25+10+1+1+1 = 6 for 63 — correct here, but:
[1,3,4] → 6: DP 2, greedy would give 4+1+1 = 3[1,3,4] for 6 is the case that kills greedy — DP finds 3+3 = 2 coins, greedy takes 4 then
needs two 1s. Naming a counterexample to the greedy approach is a strong signal, because
“why not greedy?” is the standard follow-up.
Two dimensions
def longest_common_subsequence(a, b):
"""State: dp[i][j] = LCS length of a[:i] and b[:j]."""
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # match: extend the diagonal
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one character
return dp[len(a)][len(b)]
print(f"LCS('ABCBDAB','BDCABA') = {longest_common_subsequence('ABCBDAB','BDCABA')}")
print(f"LCS('abc','abc') = {longest_common_subsequence('abc','abc')}")
print(f"LCS('abc','xyz') = {longest_common_subsequence('abc','xyz')}")
print(f"LCS('','abc') = {longest_common_subsequence('','abc')}")LCS('ABCBDAB','BDCABA') = 4
LCS('abc','abc') = 3
LCS('abc','xyz') = 0
LCS('','abc') = 0Print the table — it is the clearest way to explain the recurrence in an interview:
def lcs_table(a, b):
dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
for i in range(1, len(a)+1):
for j in range(1, len(b)+1):
dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
print(" " + " ".join(f"{c}" for c in " " + b))
for i, row in enumerate(dp):
label = " " if i == 0 else a[i-1]
print(f" {label} " + " ".join(str(v) for v in row))
lcs_table("ABCB", "BDCA") B D C A
0 0 0 0 0
A 0 0 0 0 1
B 0 1 1 1 1
C 0 1 1 2 2
B 0 1 1 2 2The value flows from the diagonal on a match and from the max of left/up otherwise. Drawing four rows of this is faster than explaining it in words.
Then the space reduction, since row i only reads row i-1:
def lcs_two_rows(a, b):
prev = [0] * (len(b) + 1)
for i in range(1, len(a) + 1):
curr = [0] * (len(b) + 1)
for j in range(1, len(b) + 1):
curr[j] = prev[j-1] + 1 if a[i-1] == b[j-1] else max(prev[j], curr[j-1])
prev = curr
return prev[len(b)]
a, b = "ABCBDAB" * 300, "BDCABA" * 300
tracemalloc.start(); longest_common_subsequence(a, b)
full = tracemalloc.get_traced_memory()[1]; tracemalloc.stop()
tracemalloc.start(); lcs_two_rows(a, b)
rows = tracemalloc.get_traced_memory()[1]; tracemalloc.stop()
print(f"full table {full/1024**2:7.1f} MB")
print(f"two rows {rows/1024**2:7.1f} MB ({full/rows:.0f}x less)")full table 148.2 MB
two rows 0.1 MB (1482x less)1,482× less memory for the same answer. The caveat to state: you lose the ability to reconstruct the actual subsequence — the full table is needed for that, so if the question asks for the sequence rather than its length, keep it.
0/1 knapsack — and the ordering trap
def knapsack(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for c in range(capacity, weights[i] - 1, -1): # BACKWARDS
dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
return dp[capacity]
def knapsack_wrong(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for c in range(weights[i], capacity + 1): # forwards — allows reuse
dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
return dp[capacity]
w, v, cap = [1, 3, 4, 5], [1, 4, 5, 7], 7
print(f"0/1 knapsack (each item once): {knapsack(w, v, cap)}")
print(f"iterating forwards: {knapsack_wrong(w, v, cap)} ← unbounded, items reused")0/1 knapsack (each item once): 9
iterating forwards: 9They agree here. Construct a case where they do not:
w2, v2, cap2 = [2], [3], 6
print(f"one item weight 2 value 3, capacity 6")
print(f" 0/1 (backwards): {knapsack(w2, v2, cap2)} ← one item, so 3")
print(f" forwards: {knapsack_wrong(w2, v2, cap2)} ← took it three times")one item weight 2 value 3, capacity 6
0/1 (backwards): 3 ← one item, so 3
forwards: 9 ← took it three times“Iterating capacity backwards means
dp[c - w]still holds the value from the previous item, so each item is used at most once. Forwards,dp[c - w]may already include this item — which is exactly the unbounded knapsack. Same three lines, different problem, and the direction of one loop is the only difference.”
Recognising it
SIGNAL STATE USUALLY IS
"how many ways to..." dp[i] = ways to reach i
"minimum / maximum cost to..." dp[i] = best value at i
"can I make / reach X?" dp[i] = bool, reachable
two sequences compared dp[i][j] over both prefixes
"with at most k of something" dp[i][k], k as a second dimension
"subarray / substring ending here" dp[i] = best ending exactly at i
choices at each step, no reuse 0/1 knapsack — iterate backwards
choices at each step, unlimited reuse unbounded — iterate forwardsThe “ending exactly at i” state is worth its own mention, because it is what makes maximum subarray linear:
def max_subarray(nums):
"""dp[i] = best sum ENDING at i. Either extend, or start fresh here."""
best = curr = nums[0]
for x in nums[1:]:
curr = max(x, curr + x)
best = max(best, curr)
return best
print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))
print(max_subarray([-3, -1, -2]))6
-1The all-negative case is the check — starting best at 0 instead of nums[0] returns 0, which
is wrong when no non-empty subarray is positive.
The procedure
1. Can I write a recursion? if not, it is not DP
2. Do subproblems repeat? count the calls — if not, use divide and conquer
3. What is the state? what varies, and what do I need to know?
4. Write the recurrence base cases first
5. Add @lru_cache now it is O(states × transitions)
6. Convert to bottom-up if depth could exceed ~1000
7. Reduce space which earlier entries does it actually read?Steps 1-4 are the work. In an interview, narrate step 3 explicitly — “my state is the index and the remaining capacity” — because a wrong state is unrecoverable and the interviewer can correct it early.
The checklist
print(coin_change([], 5), coin_change([1], 0), max_subarray([0]))
print(longest_common_subsequence("", ""))
print(climb_bottom_up(0), climb_bottom_up(1))-1 0 0
0
1 1Empty inputs, zero targets and single elements are where base cases are wrong.
Practice
1. Count how many times each subproblem is computed.
climb(1) computed 10,946 times for n=20That number is the justification for memoisation. cache_info() afterwards shows 996 hits to
501 misses, which confirms it.
2. Memoise a deep recursion and watch it still crash.
climb_memo(5000) → RecursionError
climb_bottom_up(5000) → 1045 digitsO(n) time and still a crash, because depth is stack space. That is the reason to convert to bottom-up, not style.
3. Iterate knapsack capacity forwards instead of backwards.
one item, capacity 6: backwards 3 forwards 9Forwards reuses the item — that is unbounded knapsack, a different problem. One loop direction separates them.
4. Reduce a 2-D table to two rows.
full table 148.2 MB two rows 0.1 MB1,482×. State the tradeoff: you can no longer reconstruct the actual subsequence, only its length.
Next: backtracking — generating combinations, and pruning the search.