🧠 Dynamic Programming
Define a state, write how it's built from smaller states, seed the base cases, and compute each state once.
Recognize the pattern
"Count the number of ways" to reach, build or decode something → DP that adds up the ways
"Minimum / maximum" cost, length or profit with choices at each step → DP with min / max
"Is it possible" to reach a sum, split a string, finish a path → boolean DP
Greedy looks tempting but a counterexample breaks it (coins [1, 3, 4], amount 6) → DP
A recursive brute force revisits the same arguments → add @cache, then tabulate
Two strings compared character by character → 2D dp[i][j] over prefixes
Pick items under a budget, each at most once → 0/1 knapsack, loop the budget backwards
The recipe
- State: what
dp[i]/dp[i][j]means, in words - Transition: how a state is built from smaller ones (think about the last choice)
- Base case: states you know directly (empty prefix, amount 0, first row)
- Answer:
dp[n],dp[m][n]ormax(dp)
Then choose an order where every dependency is computed first, and roll rows away if you only look back a fixed distance.
Top-down (memoized recursion)
from functools import cache
def solve(nums: list[int]) -> int:
n = len(nums)
@cache # fresh cache per call
def dp(i: int) -> int:
if i >= n: # base case
return 0
skip = dp(i + 1)
take = nums[i] + dp(i + 2)
return max(skip, take)
return dp(0)
Bottom-up 1D + O(1) space
def min_coins(coins: list[int], amount: int) -> int:
INF = float("inf")
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return -1 if dp[amount] == INF else dp[amount]
def rob(nums: list[int]) -> int:
prev, cur = 0, 0 # dp[i-2], dp[i-1]
for x in nums:
prev, cur = cur, max(cur, prev + x)
return cur
Two strings (LCS / edit distance)
def lcs(a: str, b: str) -> int:
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j],
dp[i][j - 1])
return dp[m][n]
# edit distance: dp[i][0] = i, dp[0][j] = j
# match: dp[i-1][j-1]
# else: 1 + min(dp[i-1][j], # delete
# dp[i][j-1], # insert
# dp[i-1][j-1]) # replace
Knapsack: 0/1 vs unbounded
def subset_sum(nums: list[int], target: int) -> bool:
dp = [True] + [False] * target
for x in nums: # each item once:
for s in range(target, x - 1, -1): # backwards
dp[s] = dp[s] or dp[s - x]
return dp[target]
def count_combos(coins: list[int], amount: int) -> int:
dp = [1] + [0] * amount
for c in coins: # unlimited use:
for s in range(c, amount + 1): # forwards
dp[s] += dp[s - c]
return dp[amount]
LIS in O(n log n)
import bisect
def lis(nums: list[int]) -> int:
tails = [] # tails[k]: min tail of length k+1
for x in nums:
i = bisect.bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)
Operation costs
| Operation | Time | Space |
|---|---|---|
| Plain recursion with 2 choices | O(2ⁿ) | O(n) |
| Climbing stairs / house robber | O(n) | O(1) |
| Coin change (k coins) | O(amount · k) | O(amount) |
| LIS: DP / patience + bisect | O(n²) / O(n log n) | O(n) |
| Grid paths (m × n) | O(m · n) | O(n) rolled |
| LCS / edit distance | O(m · n) | O(n) rolled |
| 0/1 knapsack (n items, budget W) | O(n · W) | O(W) |
Watch for
Wrong base case: counting problems start at dp[0] = 1, min problems at dp[0] = 0 with infinity elsewhere.
Forgetting to turn a leftover infinity into -1 (or False) for impossible answers.
0/1 knapsack in one row must loop the budget backwards; looping forwards reuses the same item.
Answer isn't always dp[-1]: LIS-style "ending at i" states need max(dp).
Deep @cache recursion (hundreds of levels) can hit the recursion limit; switch to a bottom-up table for long inputs.
@cache needs hashable arguments: pass indices or tuples, not lists, and define the cached helper inside the function so each call starts fresh.