Dynamic Programming
Classic DP Problems
Most DP questions are one of four problems wearing different clothes. Learn these and you will start recognising the shape rather than solving from scratch.
1. Climbing stairs - counting ways
You can climb 1 or 2 steps at a time. How many ways to reach step n? The answer for step n is the sum of the ways to reach the two steps you could have come from.
Counting paths
javascript
function climbStairs(n) {
let twoBack = 1
let oneBack = 1
for (let i = 2; i <= n; i++) {
;[twoBack, oneBack] = [oneBack, oneBack + twoBack]
}
return oneBack
}
console.log(climbStairs(5)) // 8It is Fibonacci with different names. Any "how many ways to reach X" problem starts here.
2. Coin change - fewest to reach a total
Minimum coins
javascript
function coinChange(coins, amount) {
// best[i] = fewest coins to make i. Infinity means impossible.
const best = new Array(amount + 1).fill(Infinity)
best[0] = 0
for (let total = 1; total <= amount; total++) {
for (const coin of coins) {
if (coin <= total && best[total - coin] + 1 < best[total]) {
best[total] = best[total - coin] + 1
}
}
}
return best[amount] === Infinity ? -1 : best[amount]
}
console.log(coinChange([1, 5, 10, 25], 30)) // 2
console.log(coinChange([5], 3)) // -1Note that greedy fails here. With coins [1, 3, 4] and a target of 6, taking the largest first gives 4+1+1 = 3 coins; the answer is 3+3 = 2. That is precisely why this is DP and not greedy.
3. Longest common subsequence - comparing sequences
LCS
javascript
function lcs(a, b) {
const table = 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++) {
table[i][j] = a[i - 1] === b[j - 1]
? table[i - 1][j - 1] + 1 // characters match
: Math.max(table[i - 1][j], table[i][j - 1]) // skip one
}
}
return table[a.length][b.length]
}
console.log(lcs("ABCBDAB", "BDCABA")) // 4O(n × m) in time and space. This is the engine behind diff tools and spell checkers - edit distance is the same table with different rules.
4. Knapsack - choosing under a limit
0/1 knapsack
javascript
function knapsack(weights, values, capacity) {
const best = new Array(capacity + 1).fill(0)
for (let i = 0; i < weights.length; i++) {
// Downwards, so each item is used at most once.
for (let c = capacity; c >= weights[i]; c--) {
best[c] = Math.max(best[c], best[c - weights[i]] + values[i])
}
}
return best[capacity]
}
console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) // 9The backwards inner loop is the whole trick. Loop forwards and you can reuse the same item repeatedly - which is the unbounded knapsack, a different problem.
Recognising which is which
- How many ways - climbing stairs.
- Fewest or smallest to reach a target - coin change.
- Comparing two sequences - LCS.
- Best value under a limit - knapsack.
Recognising which recurrence you need
Nearly every introductory DP question is one of a handful of recurrences wearing different clothes. Matching the story to the recurrence is faster than deriving from scratch.
- Choose or skip each item - 0/1 knapsack, subset sum, house robber.
- Reuse items freely - coin change, unbounded knapsack.
- Compare two sequences - edit distance, longest common subsequence.
- Best ending here - maximum subarray, longest increasing subsequence.
- Partition a range - matrix chain, burst balloons.
Coin change: fewest coins for an amount
javascript
function coinChange(coins, amount) {
// best[i] = fewest coins to make i. Infinity means unreachable.
const best = new Array(amount + 1).fill(Infinity)
best[0] = 0
for (const coin of coins) {
for (let value = coin; value <= amount; value++) {
best[value] = Math.min(best[value], best[value - coin] + 1)
}
}
return best[amount] === Infinity ? -1 : best[amount]
}
console.log(coinChange([1, 5, 6, 9], 11)) // 2 (5 + 6)Greedy fails here - taking the largest coin first gives 9 + 1 + 1, three coins. That contrast is the standard demonstration of why an exhaustive-but-cached search is needed, and it is worth being able to produce the counter-example on demand.