Dynamic Programming

Dynamic programming turns exponential brute force into polynomial time for a wide class of problems: counting ways, finding minimum costs, maximizing value under constraints, comparing sequences. diff and git use edit-distance–style DP to compare files, spell checkers use it to suggest words, and bioinformatics aligns DNA with it. It's also the topic that most rewards practice — the patterns repeat.

DP applies when a problem has two properties:

• Optimal substructure — the best answer is built from best answers to smaller versions.
• Overlapping subproblems — plain recursion would solve the same smaller version many times.

Naive recursive Fibonacci calls fib(n-2) from both fib(n) and fib(n-1), and the duplication compounds into O(2ⁿ) calls. Remember each answer and it drops to O(n).

Four steps, on paper first:

1. State — what does dp[i] (or dp[i][j]) mean, in one sentence?
2. Recurrence — how is a state built from smaller states?
3. Base cases — the smallest states you can answer directly.
4. Order — compute states so everything a state depends on is ready first.

Two ways to evaluate:

• Top-down (memoization) — write the recursion, cache results in a map or slice. Only computes the states you actually need.
• Bottom-up (tabulation) — fill a table from the base cases up with loops. No recursion overhead, and easy to shrink: if row i depends only on row i-1, keep just two rows (or one).

Time is usually number of states × work per state.

• Memo storage: a map[int]int is easy; a slice is faster when states are dense small ints. For 2-D states, use a slice of slices or a map[[2]int]int (arrays are comparable keys).
• Recursive closures (var f func(int) int; f = func…) keep the memo in scope without globals.
• Allocating a 2-D table: dp := make([][]int, rows) then make each row. One flat make([]int, rows*cols) indexed i*cols+j is faster for big tables.
• Overflow. int is 64-bit on amd64 and arm64; Fibonacci overflows it at n = 93. Counting problems often need math/big or a modulus.

Each step i costs cost[i]; you can climb one or two steps at a time and start on step 0 or 1. What's the cheapest way past the top?

// Top-down: best(i) = cheapest cost to get from step i past the top.
func minCostMemo(cost []int) int {
	memo := map[int]int{}
	var best func(i int) int
	best = func(i int) int {
		if i >= len(cost) {
			return 0 // already past the top
		}
		if v, ok := memo[i]; ok {
			return v
		}
		memo[i] = cost[i] + min(best(i+1), best(i+2))
		return memo[i]
	}
	return min(best(0), best(1))
}

// Bottom-up with O(1) space: walk backwards, keeping best(i+1) and best(i+2).
func minCostTab(cost []int) int {
	next1, next2 := 0, 0
	for i := len(cost) - 1; i >= 0; i-- {
		next1, next2 = cost[i]+min(next1, next2), next1
	}
	return min(next1, next2)
}

Same recurrence, two evaluation orders. Once you can write both, most DP problems are about finding the recurrence.

• "How many ways …?" — sum over choices.
• "Minimum / maximum cost, profit, length …" — min or max over choices.
• "Is it possible …?" — OR over choices.
• Choices at each step whose consequences ripple forward, and brute force that recomputes the same things.

The loop direction in knapsack is a classic trap: iterating capacity downward lets each item be used once; upward allows reuse (unbounded).

Part A warms up with Fibonacci both ways — a test fails if FibMemo(90) takes more than two seconds, which it would without the memo — then climbing stairs and house robber. Part B covers the main families: coin change, unique paths, LCS, edit distance, knapsack, and LIS.

go test ./10-dynamic-programming/

For each, write the state in a comment above the function before writing any code.

The files for this module

Everything below is also in the course download, in 10-dynamic-programming/. Work in exercises.go; the tests decide when you’re done.

// Package dp is Module 10: dynamic programming.
//
// DP is recursion plus remembering. For each problem, write down:
//  1. the state  — what does dp[i] (or dp[i][j]) mean, in words?
//  2. the recurrence — how is a state built from smaller states?
//  3. the base cases
//  4. the evaluation order (top-down memo, or bottom-up table)
//
// Get those four right on paper first; the code is short.
package dp

//go:build !solutions

package dp

// ============================================================
// Part A — warm-ups: the two evaluation orders
// ============================================================

// FibMemo returns the n-th Fibonacci number (F0=0, F1=1) top-down:
// plain recursion plus a memo map. Target: O(n).
func FibMemo(n int) int {
	// TODO
	return 0
}

// FibTab returns the n-th Fibonacci number bottom-up. You only ever need
// the last two values, so use O(1) space.
func FibTab(n int) int {
	// TODO
	return 0
}

// ClimbStairs returns how many distinct ways there are to climb n steps
// taking 1 or 2 steps at a time. ClimbStairs(0) = 1 (do nothing).
// State: ways[i] = ways to stand on step i.
func ClimbStairs(n int) int {
	// TODO
	return 0
}

// HouseRobber returns the max total you can take from houses in a row
// without taking two adjacent ones. [2 7 9 3 1] -> 12 (2+9+1).
// State: best total up to house i; choice: rob i or skip it. O(1) space.
func HouseRobber(nums []int) int {
	// TODO
	return 0
}

// ============================================================
// Part B — 1-D and 2-D tables
// ============================================================

// CoinChange returns the fewest coins that sum to amount (unlimited coins
// of each denomination), or -1 if impossible. [1 2 5], 11 -> 3 (5+5+1).
// State: dp[a] = fewest coins for amount a. Target: O(amount · len(coins)).
func CoinChange(coins []int, amount int) int {
	// TODO
	return 0
}

// UniquePaths counts paths from the top-left to the bottom-right of a
// rows×cols grid moving only right or down. UniquePaths(3, 7) -> 28.
// State: dp[i][j] = paths into cell (i, j) = from above + from the left.
// Challenge: use a single row of length cols.
func UniquePaths(rows, cols int) int {
	// TODO
	return 0
}

// LCS returns the length of the longest common subsequence of a and b
// (compare runes). "abcde", "ace" -> 3.
// State: dp[i][j] = LCS of the first i runes of a and first j runes of b.
func LCS(a, b string) int {
	// TODO
	return 0
}

// EditDistance returns the minimum inserts, deletes, and substitutions to
// turn a into b (Levenshtein distance, by runes). "horse", "ros" -> 3.
// Base cases: dp[i][0] = i, dp[0][j] = j.
func EditDistance(a, b string) int {
	// TODO
	return 0
}

// Knapsack returns the max total value of items (each used at most once)
// with total weight <= capacity. All weights are positive.
// weights [1 3 4 5], values [1 4 5 7], capacity 7 -> 9 (items 3+4).
// Challenge: a 1-D table iterated over capacity from high to low.
func Knapsack(weights, values []int, capacity int) int {
	// TODO
	return 0
}

// LIS returns the length of the longest strictly increasing subsequence.
// [10 9 2 5 3 7 101 18] -> 4 (2 3 7 101).
// O(n²) DP first; then try the O(n log n) "patience" version with binary
// search over the smallest tail of each length.
func LIS(nums []int) int {
	// TODO
	return 0
}

package dp

import (
	"testing"
	"time"
)

func TestFib(t *testing.T) {
	want := []int{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55}
	for n, w := range want {
		if got := FibMemo(n); got != w {
			t.Errorf("FibMemo(%d) = %d, want %d", n, got, w)
		}
		if got := FibTab(n); got != w {
			t.Errorf("FibTab(%d) = %d, want %d", n, got, w)
		}
	}
	// Plain recursion would take years at n=90; memoized it's instant.
	done := make(chan int, 2)
	go func() { done <- FibMemo(90) }()
	go func() { done <- FibTab(90) }()
	for i := 0; i < 2; i++ {
		select {
		case got := <-done:
			if got != 2880067194370816120 {
				t.Errorf("Fib(90) = %d, want 2880067194370816120", got)
			}
		case <-time.After(2 * time.Second):
			t.Fatal("Fib(90) took over 2s — is the memo actually being used?")
		}
	}
}

func TestClimbStairs(t *testing.T) {
	for _, tc := range []struct{ n, want int }{
		{0, 1}, {1, 1}, {2, 2}, {3, 3}, {5, 8}, {10, 89}, {45, 1836311903},
	} {
		if got := ClimbStairs(tc.n); got != tc.want {
			t.Errorf("ClimbStairs(%d) = %d, want %d", tc.n, got, tc.want)
		}
	}
}

func TestHouseRobber(t *testing.T) {
	for _, tc := range []struct {
		in   []int
		want int
	}{
		{[]int{1, 2, 3, 1}, 4},
		{[]int{2, 7, 9, 3, 1}, 12},
		{[]int{2, 1, 1, 2}, 4},
		{[]int{5}, 5},
		{nil, 0},
	} {
		if got := HouseRobber(tc.in); got != tc.want {
			t.Errorf("HouseRobber(%v) = %d, want %d", tc.in, got, tc.want)
		}
	}
}

func TestCoinChange(t *testing.T) {
	for _, tc := range []struct {
		coins        []int
		amount, want int
	}{
		{[]int{1, 2, 5}, 11, 3},
		{[]int{2}, 3, -1},
		{[]int{1}, 0, 0},
		{[]int{1, 3, 4}, 6, 2}, // greedy (4+1+1) gets this wrong
		{[]int{186, 419, 83, 408}, 6249, 20},
	} {
		if got := CoinChange(tc.coins, tc.amount); got != tc.want {
			t.Errorf("CoinChange(%v, %d) = %d, want %d", tc.coins, tc.amount, got, tc.want)
		}
	}
}

func TestUniquePaths(t *testing.T) {
	for _, tc := range []struct{ r, c, want int }{
		{3, 7, 28}, {3, 2, 3}, {1, 1, 1}, {1, 10, 1}, {10, 10, 48620},
	} {
		if got := UniquePaths(tc.r, tc.c); got != tc.want {
			t.Errorf("UniquePaths(%d, %d) = %d, want %d", tc.r, tc.c, got, tc.want)
		}
	}
}

func TestLCS(t *testing.T) {
	for _, tc := range []struct {
		a, b string
		want int
	}{
		{"abcde", "ace", 3},
		{"abc", "abc", 3},
		{"abc", "def", 0},
		{"AGGTAB", "GXTXAYB", 4},
		{"", "abc", 0},
		{"héllo", "hollé", 3},
	} {
		if got := LCS(tc.a, tc.b); got != tc.want {
			t.Errorf("LCS(%q, %q) = %d, want %d", tc.a, tc.b, got, tc.want)
		}
	}
}

func TestEditDistance(t *testing.T) {
	for _, tc := range []struct {
		a, b string
		want int
	}{
		{"horse", "ros", 3},
		{"intention", "execution", 5},
		{"", "abc", 3},
		{"abc", "", 3},
		{"same", "same", 0},
		{"kitten", "sitting", 3},
		{"café", "cafe", 1},
	} {
		if got := EditDistance(tc.a, tc.b); got != tc.want {
			t.Errorf("EditDistance(%q, %q) = %d, want %d", tc.a, tc.b, got, tc.want)
		}
	}
}

func TestKnapsack(t *testing.T) {
	for _, tc := range []struct {
		w, v           []int
		capacity, want int
	}{
		{[]int{1, 3, 4, 5}, []int{1, 4, 5, 7}, 7, 9},
		{[]int{10, 20, 30}, []int{60, 100, 120}, 50, 220},
		{[]int{5}, []int{10}, 4, 0},
		{[]int{2, 2, 2}, []int{3, 3, 3}, 4, 6}, // each item at most once
	} {
		if got := Knapsack(tc.w, tc.v, tc.capacity); got != tc.want {
			t.Errorf("Knapsack(%v, %v, %d) = %d, want %d", tc.w, tc.v, tc.capacity, got, tc.want)
		}
	}
}

func TestLIS(t *testing.T) {
	for _, tc := range []struct {
		in   []int
		want int
	}{
		{[]int{10, 9, 2, 5, 3, 7, 101, 18}, 4},
		{[]int{0, 1, 0, 3, 2, 3}, 4},
		{[]int{7, 7, 7, 7}, 1},
		{[]int{1, 3, 6, 7, 9, 4, 10, 5, 6}, 6},
		{nil, 0},
	} {
		if got := LIS(tc.in); got != tc.want {
			t.Errorf("LIS(%v) = %d, want %d", tc.in, got, tc.want)
		}
	}
}

//go:build solutions

package dp

import "sort"

func FibMemo(n int) int {
	memo := map[int]int{}
	var fib func(int) int
	fib = func(k int) int {
		if k < 2 {
			return k
		}
		if v, ok := memo[k]; ok {
			return v
		}
		v := fib(k-1) + fib(k-2)
		memo[k] = v
		return v
	}
	return fib(n)
}

func FibTab(n int) int {
	if n < 2 {
		return n
	}
	prev, cur := 0, 1
	for i := 2; i <= n; i++ {
		prev, cur = cur, prev+cur
	}
	return cur
}

func ClimbStairs(n int) int {
	a, b := 1, 1 // ways to reach step i-2 and i-1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

func HouseRobber(nums []int) int {
	skip, take := 0, 0 // best total if the previous house was skipped / robbed
	for _, v := range nums {
		skip, take = max(skip, take), skip+v
	}
	return max(skip, take)
}

func CoinChange(coins []int, amount int) int {
	const inf = 1 << 62
	dp := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		dp[i] = inf
		for _, c := range coins {
			if c <= i && dp[i-c] != inf {
				dp[i] = min(dp[i], dp[i-c]+1)
			}
		}
	}
	if dp[amount] == inf {
		return -1
	}
	return dp[amount]
}

func UniquePaths(rows, cols int) int {
	if rows <= 0 || cols <= 0 {
		return 0
	}
	row := make([]int, cols)
	for j := range row {
		row[j] = 1
	}
	for i := 1; i < rows; i++ {
		for j := 1; j < cols; j++ {
			row[j] += row[j-1] // above (old row[j]) + left (new row[j-1])
		}
	}
	return row[cols-1]
}

func LCS(a, b string) int {
	x, y := []rune(a), []rune(b)
	dp := make([][]int, len(x)+1)
	for i := range dp {
		dp[i] = make([]int, len(y)+1)
	}
	for i := 1; i <= len(x); i++ {
		for j := 1; j <= len(y); j++ {
			if x[i-1] == y[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[len(x)][len(y)]
}

func EditDistance(a, b string) int {
	x, y := []rune(a), []rune(b)
	dp := make([][]int, len(x)+1)
	for i := range dp {
		dp[i] = make([]int, len(y)+1)
		dp[i][0] = i
	}
	for j := 0; j <= len(y); j++ {
		dp[0][j] = j
	}
	for i := 1; i <= len(x); i++ {
		for j := 1; j <= len(y); j++ {
			if x[i-1] == y[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[len(x)][len(y)]
}

func Knapsack(weights, values []int, capacity int) int {
	dp := make([]int, capacity+1) // dp[c] = best value with capacity c
	for i, w := range weights {
		for c := capacity; c >= w; c-- { // backwards: each item used once
			dp[c] = max(dp[c], dp[c-w]+values[i])
		}
	}
	return dp[capacity]
}

func LIS(nums []int) int {
	// tails[k] = smallest tail of any increasing subsequence of length k+1.
	var tails []int
	for _, v := range nums {
		i := sort.SearchInts(tails, v)
		if i == len(tails) {
			tails = append(tails, v)
		} else {
			tails[i] = v
		}
	}
	return len(tails)
}

• Extend LCS to return the subsequence itself by walking back through the table.
• LeetCode practice: Word Break, Partition Equal Subset Sum, Longest Palindromic Subsequence.

Four questions. Answer each one in your head — or out loud — before you open the answer.

That’s the course. If every test passes, go run ./cmd/progress says so — and you’ve built every structure in it from scratch.