Dynamic Programming

⏱️ ~3-minute bite · solve the sandbox to master

0%lesson

🧒

5-Year-Old Metaphor

— The physical, real-world picture. No jargon.

📝 DP = "remember your work." A cheat sheet of answers to subproblems so you never solve the same thing twice.

The naive approach (what blows up)

Compute Fibonacci naively: fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). fib(3) is computed twice. For fib(50) that explodes to billions of redundant calls.

This is the DP signal: overlapping subproblems — you keep re-solving the exact same sub-question from scratch.

The two DP strategies

Memoization (top-down)

Write answers on post-its as you go. Recursive call hits the cache first — if the answer is already on a post-it, return it instantly.

1	const memo = new Map();
2	function fib(n) {
3	if (memo.has(n)) return memo.get(n);
4	const res = fib(n-1) + fib(n-2);
5	memo.set(n, res);
6	return res;
7	}

Tabulation (bottom-up)

Fill out the entire answer sheet in order. No recursion — just loops that build from the smallest subproblems up to the full answer.

1	function fib(n) {
2	const dp = [0, 1];
3	for (let i = 2; i <= n; i++)
4	dp[i] = dp[i-1] + dp[i-2];
5	return dp[n];
6	}

The two conditions that make DP work

Overlapping subproblems — the same smaller problem is solved repeatedly. If every subproblem is unique, you just need divide-and-conquer.

Optimal substructure — an optimal solution to the whole problem contains optimal solutions to its subproblems. (The best path from A→C through B must use the best path A→B AND the best path B→C.)

🎛️

Interactive Sandbox

— Move something, see it react instantly.

dp[0] = 0 (base case: 0 coins for amount 0)

Base case: zero coins needed to make amount 0.

1 / 8

insight

Every cell only needs coins.length lookups behind it — pure bottom-up reuse.

▶ Show Coin Change code

1	function coinChange(coins: number[], amount: number): number {
2	const dp = Array(amount + 1).fill(Infinity);
3	dp[0] = 0;
4	for (let a = 1; a <= amount; a++) {
5	for (const c of coins) {
6	if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
7	}
8	}
9	return dp[amount] === Infinity ? -1 : dp[amount];
10	}

🎯

Challenge

Explore all 5 DP patterns to master this concept. (1/5 explored)

Try it

🎯

Why Should I Care?

— The exact interview question + the bug it kills.

Exact interview question

"How do you identify that a problem is solvable with dynamic programming?"

Answer framework:

Ask: "Is the problem asking for an optimal value (min/max) or a count of ways?"
Ask: "Can I break this into smaller versions of the same problem (subproblems)?"
Ask: "Do those subproblems overlap (same sub-question appears multiple times)?"
If all yes → DP. Define state, write recurrence, identify base cases.

Memoization vs tabulation — trade-offs

	Memoization	Tabulation
Direction	Top-down (recursive)	Bottom-up (iterative)
Overhead	Call stack + hashmap	Array only, no stack
Subproblems	Solves only what's needed	Solves all states
Space opt.	Hard (recursive frames)	Easy (rolling array)

The classic DP bug: not considering all choices at each step

1	// BUG: only checks coin[0], ignores others
2	for (const coin of coins) {
3	if (coin <= a) { dp[a] = dp[a - coin] + 1; break; } // ← WRONG: first fit, not best
4	}

1	// CORRECT: try ALL coins, take the minimum
2	for (const coin of coins) {
3	if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
4	}

The bug: greedy (first/largest coin) fails for non-canonical coin systems. For coins=[1,3,5] and amount=6, greedy picks 5+1 (2 coins)… but also gets lucky here. For coins=[1,4,5] and amount=8, greedy picks 5+1+1+1 (4 coins) vs optimal 4+4 (2 coins).

🔬

The Deep Dive

— Spec refs, engine internals, the minutiae.

State transition equation derivation

The hardest part of DP is defining the state. Ask: "What do I need to know at this point to make the optimal decision?" That becomes your state variables. The recurrence then falls out of the choices available.

Coin Change derivation

State: dp[a] = min coins to make amount a.
Choice: for each coin c ≤ a, I can use it once. That leaves subproblem dp[a - c] already solved.
Recurrence: dp[a] = min(dp[a - c] + 1) for c in coins, c ≤ a

Space optimization — rolling array

Many DP tables only look back 1–2 rows. Storing the full table is wasteful. A rolling array keeps just the rows you need.

1	// Full O(n²) table → O(n) rolling for LCS
2	// Instead of dp[i][j], alternate between two rows:
3	let prev = Array(n + 1).fill(0);
4	let curr = Array(n + 1).fill(0);
5	for (let i = 1; i <= m; i++) {
6	for (let j = 1; j <= n; j++) {
7	curr[j] = s1[i-1] === s2[j-1]
8	? prev[j-1] + 1
9	: Math.max(prev[j], curr[j-1]);
10	}
11	[prev, curr] = [curr, prev.fill(0)];
12	}
13	// answer: prev[n]

For 1D DP (coin change, knapsack), iterate the capacity array backwards to avoid using an updated value in the same pass.

Common DP pattern families

Linear DP

State is one index. Examples: climb stairs, house robber, max subarray.

dp[i] = f(dp[i-1], dp[i-2], ...)

Knapsack

State is (items, capacity). 0/1 knapsack, unbounded, fractional (greedy).

dp[i][w] = max(skip, take)

Interval DP

Subproblem is a range [i,j]. Examples: burst balloons, matrix chain.

dp[i][j] = min over k in (i,j)

String DP

State is two string indices. Examples: LCS, edit distance, regex match.

dp[i][j] on (s1[0..i], s2[0..j])

Tree DP

Run DP on tree nodes via DFS. Examples: house robber on tree, max path sum.

dp[node] = f(dp[child1], dp[child2])

Digit DP

Count numbers in [lo, hi] satisfying a digit constraint. State includes position + tight flag.

dp[pos][tight][...extra] = count

Greedy vs DP

Greedy makes the locally optimal choice at each step and never revisits it. It works when a greedy choice property holds: a globally optimal solution can always be achieved by making the locally optimal choice.

DP exhaustively considers all choices and keeps the best. It works when greedy fails because taking the biggest coin (or the shortest edge) early can foreclose a better global solution.

Rule of thumb: if the problem is "minimum coins" with arbitrary denominations — DP. If it's "minimum coins" with canonical denominations (1, 5, 10, 25) — greedy works, but DP is always correct. Greedy is faster (O(n log n) vs O(n·k)) when applicable.

🎤

Interview Questions

— Real questions from real interviews — with answers.

Look for: optimization (max/min/count), overlapping subproblems, and optimal substructure — the answer can be built from answers to smaller versions of the same problem.

Top-down is recursive with a cache; bottom-up fills a table iteratively from the smallest subproblem up.

dp[i][w] = max value using items 0..i with capacity w — each item either included or excluded.

Maintain a 'patience sorting' array — replace elements using binary search to keep the array as small as possible.

Interval DP computes answers for all substrings/subranges bottom-up by length — each answer depends on answers for sub-intervals.

🎮

Memory Game

— Quick quiz — lock the concept in long-term memory.

1/4

Why might top-down DP fail on large inputs even with correct logic?