Dynamic Programming

What is Dynamic Programming?

Dynamic programming (DP) is a technique for solving problems that have two properties:

1. Optimal substructure: The optimal solution contains optimal solutions to subproblems
2. Overlapping subproblems: The same subproblems are solved multiple times

DP avoids redundant work by storing results of subproblems. That’s it. It’s not magic — it’s caching.

Top-Down (Memoization)

Start with the original problem, recurse, and cache results.

// Fibonacci — naive recursion is O(2^n), memoized is O(n)
function fib(n: number, memo = new Map<number, number>()): number {
	if (n <= 1) return n;
	if (memo.has(n)) return memo.get(n)!;

	const result = fib(n - 1, memo) + fib(n - 2, memo);
	memo.set(n, result);
	return result;
}

Bottom-Up (Tabulation)

Build the solution from smallest subproblems up. Often more space-efficient.

// Fibonacci — bottom-up, O(1) space
function fibBottomUp(n: number): number {
	if (n <= 1) return n;
	let prev = 0,
		curr = 1;

	for (let i = 2; i <= n; i++) {
		[prev, curr] = [curr, prev + curr];
	}
	return curr;
}

Classic DP Problems

Climbing Stairs

// How many ways to climb n stairs taking 1 or 2 steps at a time?
function climbStairs(n: number): number {
	if (n <= 2) return n;
	let prev = 1,
		curr = 2;

	for (let i = 3; i <= n; i++) {
		[prev, curr] = [curr, prev + curr];
	}
	return curr;
}

Longest Common Subsequence

function lcs(text1: string, text2: string): number {
	const m = text1.length,
		n = text2.length;
	const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

	for (let i = 1; i <= m; i++) {
		for (let j = 1; j <= n; j++) {
			if (text1[i - 1] === text2[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[m][n];
}

Coin Change

function coinChange(coins: number[], amount: number): number {
	const dp = new Array(amount + 1).fill(Infinity);
	dp[0] = 0;

	for (let i = 1; i <= amount; i++) {
		for (const coin of coins) {
			if (coin <= i) {
				dp[i] = Math.min(dp[i], dp[i - coin] + 1);
			}
		}
	}
	return dp[amount] === Infinity ? -1 : dp[amount];
}

Key Takeaways

1. DP = recursion + caching — nothing more mystical than that
2. Top-down is easier to write; bottom-up is often faster in practice
3. Identify the state first — the rest follows mechanically
4. Real-world uses: text diff (LCS), shortest paths (Dijkstra), compiler optimization, financial modeling