Lesson 31
Dynamic Programming
Recursion + memory: solve each subproblem once and build the answer up.
01Why it matters & the intuition
DP solves optimisation and counting problems that are exponential by brute force — edit distance (spell-check, DNA alignment), knapsack, route counting, stock trading and diff tools like git.
Think of it like…
Climbing stairs one or two steps at a time: the ways to reach step 10 are the ways to reach step 9 plus the ways to reach step 8. Write each answer on the step as you climb and you never recompute anything.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
| ε | B | D | C | A | B | A | |
|---|---|---|---|---|---|---|---|
| ε | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | ||||||
| B | 0 | ||||||
| C | 0 | ||||||
| B | 0 | ||||||
| D | 0 | ||||||
| A | 0 | ||||||
| B | 0 |
- filling
- diagonal / match
- copied max
03Key ideas
Overlapping subproblems
The same smaller question is asked many times (like fib). Caching each answer turns exponential into polynomial.
Optimal substructure
The best answer is built from best answers to smaller pieces.
Top-down vs bottom-up
Memoisation adds a cache to the recursion. Tabulation fills a table from the smallest subproblem upward — no recursion, often less memory.
The recipe
1) Define the state (what does dp[i][j] mean?). 2) Write the transition. 3) Set base cases. 4) Choose the fill order. 5) Read off the answer.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
// Longest common subsequence — the table the visualizer fills.
function lcs(a: string, b: string): number {
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 // characters match: extend diagonal
: Math.max(dp[i - 1][j], dp[i][j - 1]); // skip one character
}
}
return dp[a.length][b.length];
}
// Minimum coins to make amount (Infinity → impossible).
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let x = 1; x <= amount; x++) {
for (const c of coins) if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
}
return dp[amount] === Infinity ? -1 : dp[amount];
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Climbing stairs / Fibonacci | O(n) | O(1) with rolling vars |
| Longest common subsequence | O(m · n) | O(m · n) |
| Coin change (min coins) | O(amount · coins) | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Coin change
Write coin_change(coins, amount) returning the fewest coins that sum to amount, or -1 if impossible. Unlimited coins of each denomination.