Dynamic programming applies when a problem has two features: overlapping subproblems, meaning the same smaller instances are solved again and again, and optimal substructure, meaning an optimal solution is built from optimal solutions to those subproblems. DP solves each subproblem once and reuses the answer, turning an exponential recursion into a polynomial table fill.
The contrast with neighbors is clarifying. Divide and conquer also splits into subproblems, but they do not overlap, so there is nothing to cache. Greedy also has optimal substructure, but it commits to a local choice and never reconsiders, which DP cannot assume. When a greedy choice is not provably safe but the problem still decomposes, DP is the tool.
The recipe
Every DP is four decisions: define the state (what a subproblem index means), write the recurrence (how a state depends on smaller states), set the base cases, and choose an evaluation order so dependencies are ready when needed. You can implement it top-down with memoization (recurse and cache) or bottom-up with tabulation (fill an array in dependency order); they do the same work, and tabulation avoids recursion overhead while memoization only computes the states you actually reach.
Canonical patterns
0/1 knapsack fills $dp[c]=\max(dp[c],\,dp[c-w]+v)$ over capacities $c$, and the subtlety is iterating $c$ from high to low: a low-to-high sweep would let the same item be picked twice, which is the unbounded knapsack instead. Edit distance is a 2D recurrence,
$$dp[i][j] = \begin{cases} dp[i-1][j-1] & a_i = b_j \\ 1 + \min\big(dp[i-1][j],\, dp[i][j-1],\, dp[i-1][j-1]\big) & \text{otherwise,} \end{cases}$$
reading the three moves as delete, insert, and substitute. Longest increasing subsequence drops from the obvious $O(n^2)$ to $O(n\log n)$ by keeping a tails array, where tails[k] is the smallest possible tail of an increasing subsequence of length $k+1$; binary-searching where each value belongs keeps the array sorted and its length equal to the answer. Coin change is unbounded, so it sweeps amounts upward, allowing each coin to be reused.
Complexity is states times work per state
The running time of any DP is the number of distinct states multiplied by the work to compute one. Knapsack is $O(n \cdot \text{cap})$, edit distance $O(mn)$, coin change $O(\text{amount} \cdot \#\text{coins})$. Memory often collapses too: when a state depends only on the previous row, a rolling one-dimensional array replaces the full table.
More patterns worth memorizing
The four above are the templates; these are the higher-leverage DP problems to keep at your fingertips, grouped by shape.
- Sequence (1D): Kadane's maximum subarray, house robber (max non-adjacent sum), word break, decode ways, longest arithmetic subsequence.
- Two sequences (2D): longest common subsequence, longest common substring, distinct subsequences, and regular-expression / wildcard matching.
- Grid: minimum path sum, unique paths, maximal square, and longest increasing path in a matrix (memoized DFS over the implied DAG).
- Knapsack family: subset sum, partition into equal subsets, unbounded knapsack, coin change II (count the ways), and target sum.
- Interval DP: matrix-chain multiplication, burst balloons, longest palindromic subsequence, and optimal binary search tree.
- Subset / bitmask DP: the Held-Karp travelling salesman, assignment problems, and counting Hamiltonian paths.
- Tree DP: maximum independent set on a tree, tree diameter, and rerooting techniques.
- Digit DP: counting integers in a range that satisfy a digit constraint.
- Stock and scheduling: the best-time-to-buy-and-sell-stock family (with cooldown or fees) and weighted interval scheduling.
- Counting: Catalan-number DPs such as unique BSTs and balanced parentheses.
Step by step
- Define the state: what each subproblem index represents.
- Write the recurrence relating a state to smaller states.
- Set the base cases.
- Choose an order (or memoize) so dependencies are ready.
- Read the answer from the final state.
import bisect
def knapsack(weights, values, cap):
dp = [0] * (cap + 1)
for w, v in zip(weights, values):
for c in range(cap, w - 1, -1): # high to low: each item used once
dp[c] = max(dp[c], dp[c - w] + v)
return dp[cap]
def lis(nums): # longest increasing subsequence, O(n log n)
tails = []
for x in nums:
i = bisect.bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)
def edit_distance(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i
for j in range(n + 1): dp[0][j] = j
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]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
def coin_change(coins, amount):
INF = float('inf')
dp = [0] + [INF] * amount
for c in range(1, amount + 1):
for coin in coins:
if coin <= c:
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != INF else -1
Complexity (time and space)
Knapsack: $O(n \cdot \text{cap})$ time, $O(\text{cap})$ space. LIS here: $O(n\log n)$ time, $O(n)$ space. Edit distance: $O(mn)$ time and space, reducible to $O(\min(m,n))$ with a rolling row. Coin change: $O(\text{amount} \cdot \#\text{coins})$ time, $O(\text{amount})$ space.
Worked example
Four classic DPs on small inputs:
print(knapsack([1, 3, 4], [15, 20, 30], 4)) # 35 (items of weight 1 and 3)
print(lis([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2, 3, 7, 101)
print(edit_distance("kitten", "sitting")) # 3
print(coin_change([1, 2, 5], 11)) # 3 (5 + 5 + 1)
Follow-up questions
- DP vs greedy vs divide-and-conquer? DP needs overlapping subproblems plus optimal substructure and caches results; greedy commits to a local choice without reconsidering; divide-and-conquer splits into non-overlapping subproblems.
- Why iterate capacity downward in 0/1 knapsack? A downward sweep ensures each item is considered once; an upward sweep would reuse the same item, giving unbounded knapsack.
- Memoization vs tabulation? Same work; memoization recurses and caches (only reached states), tabulation fills bottom-up (no recursion overhead, easy to space-optimize).
- How do you reduce DP memory? If a state depends only on the previous row or a few prior states, keep a rolling array instead of the full table.
- What is optimal substructure? An optimal solution is composed of optimal solutions to its subproblems, which is what lets the recurrence combine smaller answers.
References
- Bellman, Dynamic Programming (Princeton University Press, 1957).
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS, 4th ed.).
- Skiena, The Algorithm Design Manual (3rd ed.).