69 questions using this pattern
Break problems into overlapping subproblems, storing results to avoid recomputation. This transforms exponential time complexity into polynomial by trading space for time.
Imagine building with LEGO bricks. Instead of reconstructing the same base structure every time you try a new top, you save your work. Each completed substructure becomes a building block for larger structures.
Another analogy: calculating Fibonacci numbers. To find fib(5), you need fib(4) and fib(3). But fib(4) also needs fib(3). Rather than recalculating fib(3) twice, save it the first time and reuse it.
Dynamic programming requires two properties:
Optimal substructure: The optimal solution contains optimal solutions to its subproblems.
Overlapping subproblems: The same subproblems are solved multiple times in a naive recursive approach.
The key insight is identifying the state—what information do you need to solve a subproblem? And the transition—how do you combine smaller subproblems into larger ones?
Two implementation approaches:
def coin_change(coins: list[int], amount: int) -> int: # Initialize dp with infinity; dp[0] = 0 dp = [float('inf')] * (amount + 1) dp[0] = 0 # Build solution for each amount for i in range(1, amount + 1): for coin in coins: if i - coin >= 0: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1Given coins [1, 2, 5] and amount 11, find the minimum number of coins to make exactly 11.
Example: Fibonacci with memoization
Without memoization (exponential calls):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1)
...
With memoization:
fib(5) → fib(4) → fib(3) → fib(2) → fib(1)
↓ ↓
use cached use cached
fib(3) fib(2)
Example: Coin Change (minimum coins for amount 11)
Coins: [1, 5, 6] Amount: 11
dp[0] = 0 (base case: 0 coins for amount 0)
dp[1] = dp[0] + 1 = 1 (use coin 1)
dp[5] = min(dp[4]+1, dp[0]+1) = 1 (use coin 5)
dp[6] = min(dp[5]+1, dp[0]+1) = 1 (use coin 6)
dp[11] = min(dp[10]+1, dp[6]+1, dp[5]+1)
= min(?, 2, 3)
= 2 (6 + 5)
Use this skeleton as a starting point for problems using this pattern:
# Top-down (memoization)
from functools import lru_cache
def solve_top_down(n: int) -> int:
@lru_cache(maxsize=None)
def dp(state):
# Base case
if base_condition(state):
return base_value
# Recursive case with memoization
result = initial_value
for choice in choices(state):
subproblem = dp(next_state(state, choice))
result = combine(result, subproblem)
return result
return dp(initial_state(n))
# Bottom-up (tabulation)
def solve_bottom_up(n: int) -> int:
# Initialize DP table
dp = [initial_value] * (n + 1)
# Base case
dp[0] = base_value
# Fill table iteratively
for i in range(1, n + 1):
for choice in choices(i):
if valid(i, choice):
dp[i] = combine(dp[i], dp[prev_state(i, choice)])
return dp[n]
# 2D DP example (Longest Common Subsequence)
def lcs(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[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]Look for these keywords and patterns in problem descriptions:
Choosing a state that doesn't capture all necessary information leads to incorrect transitions or missing cases.
Fix:
Ask: "What do I need to know to solve this subproblem?" The answer defines your state. Test with small examples to verify.
Incorrect initialization causes wrong answers to propagate through the entire DP table.
Fix:
Think about the smallest/simplest subproblem. What's the answer when there's nothing left to consider? Start from there.
Single dimension state, typically indexed by position or remaining capacity. Common for linear sequences.
Examples: Climbing Stairs, House Robber, Coin Change
Two-dimensional state, often for comparing two sequences or tracking two variables (position and capacity).
Examples: Longest Common Subsequence, Edit Distance, 0/1 Knapsack
State represents a range [i, j]. Solve for all subranges and combine. Often O(n^3) time.
Examples: Burst Balloons, Matrix Chain Multiplication
State includes a bitmask representing a subset. Used when order matters among a small set of items.
Examples: Traveling Salesman, Shortest Superstring
State associated with tree nodes. Transition from children to parent (or vice versa).
Examples: House Robber III, Binary Tree Maximum Path Sum
Start here to build foundational understanding.
Master the pattern with these representative problems.
Test your mastery with complex variations.
Explore similar techniques:
Make locally optimal choices at each step, hoping to find a global optimum. Greedy algorithms are simple and efficient but only work when the problem has the greedy choice property—local optima lead to global optimum.
Build solutions incrementally, exploring choices one at a time and abandoning paths that fail to satisfy constraints. Backtracking systematically explores all possibilities by making a choice, recursing, then undoing the choice.
Confusion about whether dp[i] represents the first i elements or the element at index i causes index errors.
Fix:
Be consistent. Common convention: dp[i] = answer for first i elements, so dp[0] = empty case. Indices in strings/arrays are 0-based.
Not returning infinity for minimum problems or 0 for counting when a state is unreachable gives wrong aggregations.
Fix:
Initialize dp with appropriate "impossible" values (infinity for min, -infinity for max, 0 for counting). Return -1 if final answer is still impossible.
Using O(n*m) space when only the previous row/column is needed wastes memory on large inputs.
Fix:
If dp[i] only depends on dp[i-1], use two arrays (current and previous) or even a single array updated carefully.