Part 1 · Concepts · Dynamic programming
Dynamic programming
Solve a problem from answers to smaller versions of it, and never compute the same smaller answer twice.
How it works
Steps: 1) Define the state ('best[a] = fewest coins for amount a'). 2) Write the transition from smaller states. 3) Base cases. 4) Order: top-down with a memo (recursion plus a Map), or bottom-up filling a table. Coin change: best[a] = min over coins of best[a - c] + 1. LCS: if the characters match, take the diagonal + 1, otherwise the best of skipping one character. 0/1 knapsack: loop capacity backwards so each item is used once.
| cost | number of states × work per state |
| coin change | O(amount × coins) |
| LCS | O(n × m) |
| knapsack | O(items × capacity) |
Reach for it when
- 'How many ways', 'minimum cost', 'maximum value', 'is it possible'
- Choices whose sub-results repeat
- Greedy fails on a counterexample
Implementation (JavaScript, tested)
// Fewest coins to make `amount`, or -1. Unlimited coins of each type.
function coinChange(coins, amount) {
const best = new Array(amount + 1).fill(Infinity);
best[0] = 0;
for (let a = 1; a <= amount; a++)
for (const c of coins) if (c <= a) best[a] = Math.min(best[a], best[a - c] + 1);
return best[amount] === Infinity ? -1 : best[amount];
}
// Longest common subsequence length (the idea behind diff tools)
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++)
dp[i][j] =
a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
return dp[a.length][b.length];
}
// 0/1 knapsack: each item once, max value within capacity. 1D table, loop capacity backwards.
function knapsack(weights, values, cap) {
const dp = new Array(cap + 1).fill(0);
for (let i = 0; i < weights.length; i++)
for (let c = cap; c >= weights[i]; c--) dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
return dp[cap];
}Traps
- Greedy coin change fails for coins [1, 3, 4] and amount 6 (greedy says 3 coins, DP finds 2).
- Knapsack looped forwards lets an item be reused.
- Start with the recursive version out loud, then add memo. It's easier to explain.
In real systems: diff tools are built on LCS-style edit distance (git uses Myers' algorithm). Spell checkers use edit distance. Pricing and resource allocation are knapsack-shaped.
Say out loud: The subproblems overlap, so I'll memoize. The state is X, the transition is Y, and the cost is states times work per state.