Dynamic Programming
Solve a problem by breaking it into overlapping sub-problems and remembering each answer. Top-down vs bottom-up, coin change, LCS, and knapsack.
advanced55 min#dynamic-programming#memoization#tabulation#optimization
Prerequisites: Recursion, Arrays and Dynamic Arrays
Why it matters
Dynamic programming (DP) turns problems that look exponential into polynomial ones. Route planning, spell correction (edit distance), diffing files (longest common subsequence), resource allocation, and text layout all rely on it. It also has a reputation as the hardest interview topic, mostly because people memorize solutions instead of learning the method for finding the state. The method is learnable.
Intuition
Suppose you are asked for the fewest coins that make 10 using coins 1, 5 and 6. If you already knew the answer for 9, for 5, and for 4, you would just add one coin to the best of them. And to know the answer for 9 you would ask the same question again for smaller amounts. A naive recursion asks about the same amounts over and over, a tree of repeated work. DP says: compute each distinct question once, write the answer down, and reuse it.
A picture of the repeated work, using the Fibonacci recursion fib(4), where each call asks for the two before it.
Two properties must hold:
- Overlapping sub-problems: the same smaller questions recur. (If they never repeat, plain divide and conquer is enough.)
- Optimal substructure: the best answer to the big problem is built from best answers to smaller ones.
How it works
Finding the state is the real skill. Ask: what is the smallest set of numbers that fully describes "where I am" in the problem, so that the future depends only on it?
- Coin change: the remaining amount.
state = (rem). - Longest common subsequence: how much of each string is consumed.
state = (i, j). - 0/1 knapsack: which item we are deciding on and remaining capacity.
state = (item, cap).
Then write the recurrence: how does the answer for a state follow from smaller states? For coin change, best(rem) = 1 + min(best(rem - c) for each coin c). Finally set the base cases (best(0) = 0) and decide the order.
There are two equivalent ways to evaluate.
Top-down (memoization): write the natural recursion, then cache results by state. Easy to derive and only computes the states actually reached. Cost: recursion depth and call overhead.
Bottom-up (tabulation): fill a table from the smallest states up so that every dependency is ready when needed. No recursion, easy to optimize memory. Cost: you must get the order right.
The same idea with the intro example, fewest coins to make 10 using coins 1, 5 and 6, as a one-dimensional table.
The index under each cell is the amount. Each cell looks back at dp[x - coin] for every coin and keeps the smallest result plus one.
LCS table for "ABC" vs "AC" "" A C
"" 0 0 0
A 0 1 1
B 0 1 1
C 0 1 2
Match: take diagonal + 1. Otherwise: max(up, left).
Here is the "ABC" versus "AC" table from above, filled one cell at a time. Green is the cell being computed, amber are the cells it reads.
Every cell is computed from at most three neighbours that are already filled. That fixed fill order is what makes bottom-up work.
Space optimization. If a row depends only on the previous row (or a state depends only on earlier cells of one array), keep just that. The knapsack below uses a single array and loops capacity backwards so each item is used at most once. Loop forwards and you accidentally allow unlimited copies (the unbounded knapsack, which is a different problem).
| Operation | Time | Notes |
|---|---|---|
| Naive recursion (coin change) | Exponential | Recomputes the same amounts |
| Coin change, DP | O(amount * coins) | One cell per amount, one try per coin |
| LCS of lengths m and n | O(m * n) | Table size; O(min(m, n)) space possible |
| 0/1 knapsack | O(items * capacity) | Pseudo-polynomial in the capacity value |
| Memoization overhead | O(states) space | Plus recursion depth for top-down |
Code: coin change, LCS, knapsack
from functools import lru_cache
def coin_change_top_down(coins, amount):
@lru_cache(maxsize=None)
def best(rem): # fewest coins to make rem
if rem == 0:
return 0
if rem < 0:
return float("inf")
return 1 + min(best(rem - c) for c in coins)
ans = best(amount)
return -1 if ans == float("inf") else ans
def coin_change_bottom_up(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount # dp[x] = fewest coins for x
for x in range(1, amount + 1):
for c in coins:
if c <= x and dp[x - c] + 1 < dp[x]:
dp[x] = dp[x - c] + 1
return -1 if dp[amount] == INF else dp[amount]
def lcs(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):
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[-1][-1]
def knapsack(weights, values, cap):
dp = [0] * (cap + 1) # dp[w] = best value with capacity w
for wt, val in zip(weights, values):
for w in range(cap, wt - 1, -1): # backwards: each item used once
dp[w] = max(dp[w], dp[w - wt] + val)
return dp[cap]
print(coin_change_top_down((1, 5, 6), 10), coin_change_bottom_up((1, 5, 6), 10))
print(coin_change_bottom_up((2,), 3))
print(lcs("ABCBDAB", "BDCABA"))
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))function coinChangeTopDown(coins, amount) {
const memo = new Map();
function best(rem) { // fewest coins to make rem
if (rem === 0) return 0;
if (rem < 0) return Infinity;
if (memo.has(rem)) return memo.get(rem);
let res = Infinity;
for (const c of coins) res = Math.min(res, 1 + best(rem - c));
memo.set(rem, res);
return res;
}
const ans = best(amount);
return ans === Infinity ? -1 : ans;
}
function coinChangeBottomUp(coins, amount) {
const dp = [0, ...new Array(amount).fill(Infinity)]; // dp[x] = fewest coins for x
for (let x = 1; x <= amount; x++) {
for (const c of coins) {
if (c <= x && dp[x - c] + 1 < dp[x]) dp[x] = dp[x - c] + 1;
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
function lcs(a, b) {
const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[a.length][b.length];
}
function knapsack(weights, values, cap) {
const dp = new Array(cap + 1).fill(0); // dp[w] = best value with capacity w
weights.forEach((wt, i) => {
for (let w = cap; w >= wt; w--) { // backwards: each item used once
dp[w] = Math.max(dp[w], dp[w - wt] + values[i]);
}
});
return dp[cap];
}
console.log(coinChangeTopDown([1, 5, 6], 10), coinChangeBottomUp([1, 5, 6], 10));
console.log(coinChangeBottomUp([2], 3));
console.log(lcs("ABCBDAB", "BDCABA"));
console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7));Both versions print four lines: 2 2 (top-down and bottom-up agree: 5 + 5), -1 (3 cannot be made from coin 2), 4 (the LCS of "ABCBDAB" and "BDCABA" has length 4), and 9 (best knapsack value at capacity 7, taking the weights 3 and 4).
Common pitfalls
- Wrong or incomplete state: if the answer also depends on something not in your state (like whether you used a skip yesterday), add it to the state.
- Wrong iteration order: bottom-up needs every dependency computed before use. Loop capacity backwards for 0/1 knapsack, forwards for unbounded.
- Mutable default cache or shared memo: reusing a memo across calls with different inputs (like different coin lists) returns stale answers.
- Using infinity carelessly:
inf + 1is fine in both Python and JavaScript, but sentinel integers like10**9can overflow in other languages. Always convert an unreachable result to a clear answer such as-1. - Assuming greedy works: with coins 1, 5, 6 and amount 10, greedy takes 6 and four 1s (5 coins) while DP finds 5 + 5 (2 coins).
- Recursion limit: Python's default depth is about 1000. Prefer bottom-up for deep problems.
Practice
Climbing stairs easy
Hint
To reach step n you came from step n-1 or n-2. Does that look familiar?
Show solution
ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1. This is the Fibonacci recurrence. Bottom-up with two variables gives O(n) time and O(1) space.
House robber medium
Hint
At each house you either skip it or rob it and skip the previous one.
Show solution
Let best[i] be the most money from the first i houses. Then best[i] = max(best[i - 1], best[i - 2] + money[i - 1]). Only the last two values matter, so keep two variables. O(n) time, O(1) space.
Edit distance medium
Hint
State is (i, j): prefixes of the two words. There are three operations to consider on a mismatch.
Show solution
dp[i][j] is the fewest edits to turn the first i characters of a into the first j of b. If the characters match, copy dp[i-1][j-1]. Otherwise it is 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)). Base cases are dp[i][0] = i and dp[0][j] = j. O(m * n).
Partition equal subset sum hard
Hint
If the total is odd the answer is no. Otherwise it is a yes/no knapsack with target total / 2.
Show solution
Use a boolean array reach of size target + 1 with reach[0] = true. For each number, loop s from target down to the number and set reach[s] = reach[s] or reach[s - num]. Answer is reach[target]. O(n * target) time, O(target) space.
Interview questions
- How do you tell a problem needs DP? It asks for a count, a minimum or maximum, or a yes/no over choices, and a brute-force recursion would repeat the same sub-calls.
- Top-down or bottom-up? Top-down is quicker to write and skips unreachable states; bottom-up avoids recursion limits and enables rolling arrays. Both have the same asymptotic time.
- What is the difference between DP and greedy? Greedy commits to one local choice and never reconsiders. DP considers all choices for each sub-problem and keeps the best, so it is slower but correct on more problems.
- Why is knapsack called pseudo-polynomial? Its runtime depends on the numeric value of the capacity, not just the number of bits needed to write it down.
Interviewers look for: a clearly stated state and recurrence before any code, correct base cases, and an explicit complexity of states times transitions.
Quick check
In the single-array 0/1 knapsack, why do we loop the capacity from high to low for each item?
Finished this lesson?
Further resources
- Dynamic programming (Wikipedia) (article)
- Optimal substructure (Wikipedia) (article)
- Knapsack problem (Wikipedia) (article)
- Python docs: functools.lru_cache (docs)