Dynamic Programming

The Idea

Dynamic programming applies when a problem can be answered by combining answers to smaller versions of itself, and when those smaller versions repeat.

Overlapping Subproblems

Plain recursion on Fibonacci computes fib(n-2) twice: once directly, and once inside fib(n-1). Those two calls each repeat their own work, and the repetition multiplies. The number of calls grows as fast as the answer itself. Demo of four versions of the same recurrence with call counts: 50_memo_tabulation.go.

The number of distinct subproblems is only n − 1, but the plain recursion solves them millions of times. If you can count the distinct subproblems and each one is cheap to solve from smaller ones, you can count the cost of DP: number of states × work per state. This is the same "recursion tree with repeated nodes" that the Recursion lesson warned about, now with the fix.

The Five-Step Recipe

Every DP in this lesson is designed with the same five questions. Write the answers down before any code:

1. State. What few numbers describe one subproblem completely? ("the first i items and capacity w")
2. Meaning. Say in one sentence what the table entry means. ("best[i][w] is the most value using only the first i items with capacity w")
3. Recurrence. How does a state's answer follow from smaller states? (take the item, or leave it)
4. Base cases. Which states have an obvious answer that needs no recurrence? (no items: value 0)
5. Order and answer. In which order can states be filled so that every dependency is ready, and which state holds the final answer?

Most wrong DPs fail at step 2: the entry means two slightly different things in two places. A precise sentence prevents that.

Top-Down or Bottom-Up

The same recurrence can be run in two ways:

// Top-down (memoization): keep the recursion, add a cache.
func fibMemo(n int, memo map[int]int) int {
	if n < 2 {
		return n
	}
	if v, ok := memo[n]; ok {
		return v // already solved: no recursion
	}
	v := fibMemo(n-1, memo) + fibMemo(n-2, memo)
	memo[n] = v
	return v
}

// Bottom-up (tabulation): fill the table in an order that has every
// dependency ready.
func fibTable(n int) int {
	if n < 2 {
		return n
	}
	f := make([]int, n+1)
	f[1] = 1
	for i := 2; i <= n; i++ {
		f[i] = f[i-1] + f[i-2]
	}
	return f[n]
}

A good workflow: write the plain recursion and get it correct on small inputs, add a cache, and only then convert to a table if speed or memory needs it.

Shrinking the Table

When a state reads only the last few entries, the rest can be thrown away. fibRolling keeps two variables instead of a slice. Two-dimensional tables often keep one row (the 0/1 knapsack below) or two rows. This matters when the table is large, but only after the version with the full table is correct, because the full table is also what you walk backward to recover the choices.

Warm-Up Problems

Four short problems, each with a state you can guess from the wording. All are in 50_memo_tabulation.go.

Counting Paths in a Grid

Move only right or down from the top-left cell to the bottom-right cell, avoiding walls. The state is a cell. There are two natural meanings, and both are correct:

• Top-down: pathsFrom(r, c) is the number of paths from this cell to the goal.
• Bottom-up: ways[r][c] is the number of paths from the start to this cell, so ways[r][c] = ways[r-1][c] + ways[r][c-1], and a wall has 0 ways.

On a 12 × 12 grid with no walls there are 705,432 paths. Plain recursion makes 3,997,447 calls; with a cache it makes 287 calls for 144 cells. The demo checks both directions against each other and against plain recursion on 2,000 random grids.

Cheapest Path, and Recovering the Route

Give each cell a cost, and find the cheapest path. The recurrence is best[r][c] = cost[r][c] + min(best[r-1][c], best[r][c-1]). The table answers how much. To answer which route, walk backward from the goal: at each cell step to the neighbour with the smaller total. Every DP in this lesson recovers its choices this way, by re-reading the table instead of storing extra data.

r, c := rows-1, cols-1
for {
	route = append(route, [2]int{r, c})
	if r == 0 && c == 0 {
		break
	}
	if r == 0 || (c > 0 && best[r][c-1] <= best[r-1][c]) {
		c--
	} else {
		r--
	}
}

House Robber: a State That Needs Two Numbers

Choose houses to rob, never two neighbours. Let take[i] be the best loot using only the first i houses. House i is either skipped (take[i-1]) or robbed, which forces skipping house i − 1 (take[i-2] + loot):

func robber(loot []int) int {
	prev2, prev1 := 0, 0 // best for i-2 and i-1 houses
	for _, v := range loot {
		prev2, prev1 = prev1, max(prev1, prev2+v)
	}
	return prev1
}

Only the last two answers are ever read, so the table has shrunk to two variables. The demo compares it with all 2ⁿ subsets on 3,000 random inputs.

The Knapsack Family

Knapsack, coin change, and subset sum are one DP in three disguises. The state is "how much capacity (amount, sum) is left", and at each item there is a choice. They solve exactly the cases where greedy failed in Greedy Algorithms. Demo with every variant checked against brute force: 51_knapsack_family.go.

The same items as the greedy counterexample. Walking back from the corner finds the tent and the stove: value 40, where greedy by value per kilo reached 35.

0/1 Knapsack

Each item can be taken once. State: best[i][w], the most value using only the first i items with capacity w. For each item there are two choices, and the answer is the larger:

• leave it: best[i-1][w]
• take it (if it fits): best[i-1][w - weight] + value

for i := 1; i <= n; i++ {
	it := items[i-1]
	for w := 0; w <= capacity; w++ {
		best[i][w] = best[i-1][w] // leave it
		if it.weight <= w {
			best[i][w] = max(best[i][w], best[i-1][w-it.weight]+it.value) // or take it
		}
	}
}

The table costs O(n · capacity) time and memory. To find which items were taken, walk back from best[n][capacity]: if the value differs from the row above, that item was taken, and you continue with the smaller capacity. The demo checks the value, the rolling version below, and that the reported items fit and add up, on 3,000 random instances.

Loop Direction Decides the Problem

Row i only reads row i − 1, so one row is enough, if you update capacities from high to low:

func knapsackRolling(items []Item, capacity int) int {
	best := make([]int, capacity+1)
	for _, it := range items {
		for w := capacity; w >= it.weight; w-- { // downward: each item once
			best[w] = max(best[w], best[w-it.weight]+it.value)
		}
	}
	return best[capacity]
}

Going down guarantees that best[w - weight] has not been touched yet by the current item, so it still means "without this item". Flip the loop to go up and best[w - weight] may already include the item, so the item can be taken again and again. That is the unbounded knapsack, a different problem. With one item (weight 3, value 10) and capacity 9, the downward loop gives 10 and the upward loop gives 30. Both loops are correct for their own problem; the bug is using the wrong one.

Coin Change

The fewest coins that pay an amount (unlimited coins of each value) is an unbounded problem over amounts. State: fewest[a]. The last coin is some coin c, so fewest[a] = 1 + min(fewest[a - c]) over coins c ≤ a. For coins {4, 3, 1} and amount 6 the answer is 2 (3 + 3), where greedy needed 3 coins. For coins {5, 3} and amount 7 the table reports that no payment exists, with the value -1 in the demo.

Counting: Combinations or Sequences?

To count the ways to pay an amount, the order of the two loops decides what is counted:

// combinations: coins in the OUTER loop
for _, c := range coins {
	for a := c; a <= amount; a++ {
		ways[a] += ways[a-c]
	}
}

// sequences: amount in the OUTER loop
for a := 1; a <= amount; a++ {
	for _, c := range coins {
		if c <= a {
			ways[a] += ways[a-c]
		}
	}
}

With coins in the outer loop, each coin is fully decided before the next is considered, so 1 + 2 and 2 + 1 are the same set. With the amount in the outer loop, every coin is a candidate for the last step at every amount, so different orders count separately. For amount 4 and coins {1, 2, 3} the first counts 4 combinations and the second counts 7 sequences. Nothing else changes between the two loops, which makes it an easy mistake.

Subset Sum

Can some of the numbers add up to exactly the target? State: reachable[s], a boolean. It is the 0/1 knapsack with booleans, and the same downward loop applies. Can this list be split into two groups with equal sums? is subset sum with target total / 2.

Pseudo-Polynomial Time

The table has n · capacity cells. Doubling the capacity doubles the work, but adding one digit to the number multiplies it by ten. So the time is polynomial in the value of the capacity, not in the size of its representation: this is called pseudo-polynomial. It is fine for a capacity of ten thousand and hopeless for a capacity of 10¹⁸. The knapsack problem is NP-hard in general, and this DP is not a contradiction: it is fast only when the numbers are small.

Sequence Problems

When the input is one or two sequences, the state is usually a prefix (or a pair of prefixes): "the answer for the first i elements". Each table is also walked backward to recover the answer itself. Demo with brute-force oracles for all of them: 52_sequence_dp.go.

Subsequence vs Substring

A subsequence keeps the order but may skip elements: "ace" is a subsequence of "abcde". A substring must be contiguous. The problems below are about subsequences, which is what makes them exponential to brute-force: a sequence of n items has 2ⁿ subsequences.

Longest Increasing Subsequence

State: length[i], the longest strictly increasing subsequence that ends at index i. It extends the best earlier subsequence whose last element is smaller: length[i] = 1 + max(length[j]) over j < i with a[j] < a[i]. That is O(n²). The state "ends at i" is a common trick: it makes the recurrence easy to write, and the final answer is the maximum over all i.

The O(n log n) version keeps tails[k], the smallest possible last element of an increasing subsequence of length k + 1. The slice is always sorted, so the place for the next element is found by binary search, exactly as in Searching:

func lisFast(a []int) int {
	var tails []int
	for _, x := range a {
		pos, _ := slices.BinarySearch(tails, x) // first tail >= x
		if pos == len(tails) {
			tails = append(tails, x)
		} else {
			tails[pos] = x
		}
	}
	return len(tails)
}

Note that tails is not itself the subsequence; only its length is the answer. The demo checks both versions and the reconstructed sequence against all subsets.

Longest Common Subsequence

State: l[i][j], the LCS length of the first i items of one sequence and the first j of the other. If the last items are equal, use them; otherwise one of them is not needed:

for i := 1; i <= len(a); i++ {
	for j := 1; j <= len(b); j++ {
		if a[i-1] == b[j-1] {
			l[i][j] = l[i-1][j-1] + 1
		} else {
			l[i][j] = max(l[i-1][j], l[i][j-1])
		}
	}
}

For "ABCBDAB" and "BDCABA" the answer is "BCBA". Walking back from the corner (match: take it and go diagonally; otherwise go toward the larger neighbour) recovers the subsequence itself. A longest palindromic subsequence is the LCS of a string and its reverse: "character" gives "carac".

Application: diff

A file comparison tool is an LCS over lines. The lines in the LCS are unchanged; everything else was removed from the old file or added to the new one. The demo's diff function walks the LCS table and prints the familiar output:

  package main
+
+ import "fmt"

  func main() {
-     println("hi")
+     fmt.Println("hi")
  }

The check rebuilds the new file from the "kept" and "added" lines and confirms the kept lines are exactly an LCS. Real tools add heuristics for speed on huge files, but the core is this table.

Edit Distance

The fewest single-character insertions, deletions, and substitutions that turn one string into another. It powers spell checkers, fuzzy search, and DNA alignment. State: d[i][j] = edits to turn the first i letters of one string into the first j of the other. The three edits are the three neighbours:

if a[i-1] == b[j-1] {
	d[i][j] = d[i-1][j-1]
} else {
	d[i][j] = 1 + min(d[i-1][j-1], d[i-1][j], d[i][j-1])
}

The base cases are d[i][0] = i (delete everything) and d[0][j] = j (insert everything).

The table for "kitten" and "sitting". The green path is the edit script; the value in the corner is the distance.

The path in the picture is the edit script: sub k→s, keep i, keep t, keep t, sub e→i, keep n, ins g. The demo applies the script to the first string and checks that it produces the second, that its cost equals the table value, and that the value matches plain recursion on 3,000 random pairs.

Intervals and Partitions

Some problems ask for the best way to cut a sequence into pieces or to combine neighbours in the best order. Two state shapes cover most of them. Demo with four problems checked against plain recursion: 53_interval_partition_dp.go.

Fill Short Intervals First

A long interval is built from shorter intervals inside it, so the shorter ones must be ready. The outer loop is therefore over the length, not over the start. Looping over the start in increasing order reads cells that are not yet filled, and the answer is silently wrong.

Matrix Chain Multiplication

Multiplying an (a × b) matrix by a (b × c) matrix costs a·b·c scalar multiplications. The product of a chain is the same for every order of parentheses, but the cost is not. For matrices of size 10×30, 30×5, and 5×60, the order (AB)C costs 4,500 multiplications and A(BC) costs 27,000. State: cost[i][j], the cheapest way to multiply matrices i to j. Try every last multiplication, splitting after matrix k:

for length := 2; length <= n; length++ { // short intervals first
	for i := 0; i+length-1 < n; i++ {
		j := i + length - 1
		cost[i][j] = 1 << 60
		for k := i; k < j; k++ {
			c := cost[i][k] + cost[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
			if c < cost[i][j] {
				cost[i][j], split[i][j] = c, k
			}
		}
	}
}

Storing the best split point, split[i][j], lets a short recursive function print the parenthesization. The cost is O(n³): n² states with n choices each.

Think About the Last Action

Burst balloons: bursting balloon k earns nums[left] · nums[k] · nums[right] for its current neighbours, and the goal is the maximum total for bursting all of them. Asking "which balloon do I burst first?" is a trap: bursting it changes the neighbours of the others, so the two sides depend on each other.

Ask instead: "which balloon do I burst last in this interval?" When k is last, its neighbours are the fixed edges of the interval, and everything on its two sides was burst independently before. That gives a clean recurrence:

for k := l + 1; k < r; k++ {
	best[l][r] = max(best[l][r], best[l][k]+best[k][r]+v[l]*v[k]*v[r])
}

Turning a problem around, from "first" to "last" or from "add" to "remove", is one of the most useful moves in DP design. The demo checks the last-balloon table against a brute force that tries every bursting order.

Cutting a Sequence into Pieces

Word break: in how many ways can a text be cut into dictionary words? The last word is s[j:i] for some j < i, so ways[i] is the sum of ways[j] over all j where s[j:i] is a word. With the dictionary {cat, cats, and, sand, dog}, "catsanddog" has 2 ways ("cats and dog" and "cat sand dog"), and "catsandog" has none. Storing where the last word starts lets you print one segmentation.

Palindrome partitioning: fewest cuts so that every piece is a palindrome. It needs two tables. isPal[i][j] is an interval table (equal ends and a palindrome inside). pieces[i] is a prefix table: 1 + the fewest pieces for a shorter prefix s[:j], over every j where s[j..i-1] is a palindrome. Combining an interval table with a prefix table is common in harder problems. For "racecarxyz" the answer is 3 cuts: racecar | x | y | z.

Sets and Modes

Two more state designs appear constantly. Demo with both, checked against permutations and against every sequence of actions: 54_bitmask_state_dp.go.

Bitmask DP: The State Is a Set

When the choices are "which subset of n items have I used?", store the subset in one integer: bit i is 1 when item i is used. There are 2ⁿ subsets, so it works up to n around 20, but it is vastly better than trying all n! orders.

Travelling salesman (Held-Karp): visit every city once and return to city 0 by the shortest tour. State: best[mask][last], the cheapest way to start at city 0, visit exactly the cities in mask, and stand at city last. From there, move to any city not in the mask:

for mask := 1; mask <= full; mask++ {
	for last := 0; last < n; last++ {
		if best[mask][last] == inf {
			continue
		}
		for next := 0; next < n; next++ {
			if mask>>next&1 == 1 {
				continue // already visited
			}
			m2 := mask | 1<<next
			if c := best[mask][last] + d[last][next]; c < best[m2][next] {
				best[m2][next], from[m2][next] = c, last
			}
		}
	}
}

The cost is O(2ⁿ · n²), against (n − 1)! for permutations. For 16 cities the DP handles about a million states in tens of milliseconds, while trying all orders would mean about 1.3 × 10¹² tours. The demo confirms both the length and the reported tour against every permutation for up to 8 cities. The assignment problem (one job per worker at minimum cost) shows a useful shortcut: the number of workers already placed is bits.OnesCount(mask), so the next worker's index need not be stored in the state.

State Machines: The State Is a Mode

Sometimes the state is the position plus a small mode. Buying and selling a stock, one share at a time, has modes hold, sold, and rest. Draw the modes as boxes and the allowed moves as arrows, and each day's recurrence follows the arrows into each box. With a one-day cooldown after selling (you cannot buy on the day after a sale):

for _, p := range prices {
	newHold := max(hold, rest-p) // keep holding, or buy today from "rest"
	newSold := hold + p          // sell today what we were holding
	newRest := max(rest, sold)   // idle; a sale yesterday ends its cooldown
	hold, sold, rest = newHold, newSold, newRest
}
return max(sold, rest) // never end while holding: that share is unsold

Buying comes only from rest, not from sold, and that one arrow is the whole cooldown rule. A variant with at most k transactions adds a counter to the mode. The demo checks both against a brute force that tries every assignment of "nothing, buy, sell" to every day and keeps the valid ones. State machines like these also parse text, model game turns, and validate protocols.

Designing a DP

The recipe from the start of the lesson, applied to a new problem, has a few habits that help.

Finding the State

• Start from the brute force. Write the recursion that tries everything. The arguments that change between calls are the candidate state.
• Keep only what the future needs. If a value is never read by later choices, remove it from the state. If a later choice depends on something, the state must contain it.
• Prefer prefixes, intervals, and "ends at i". These three shapes cover most sequence problems.
• Count the states. If the table is too big, look for a smaller state (as with the worker index in the assignment problem) or a different problem shape.

DP, Greedy, or Backtracking?

Debugging a DP

Write the brute force first, on inputs small enough to enumerate, and compare on thousands of random inputs, exactly as every demo here does. When they disagree, print the table for a tiny failing input and check each cell by hand against the sentence that defines it. The bug is nearly always a base case, a loop direction, or an entry with two meanings.

Common Pitfalls

DP bugs give plausible numbers, so compare with a slow oracle.

Loop Direction and Loop Order

In a one-row knapsack, high-to-low means "each item once" and low-to-high means "unlimited". When counting ways, coins in the outer loop count sets and amounts in the outer loop count sequences. In interval DP, length must be the outer loop. Check these three every time you write a nested loop.

Wrong or Missing Base Cases

An empty prefix, a single element, and an amount of zero each need an explicit answer. For "ways" it is usually 1 (the empty choice); for "minimum" it is 0; for "impossible" it is a large sentinel. Adding to a sentinel such as math.MaxInt overflows, as in Shortest Paths; use a value like 1 << 30 and test for it before adding.

A State That Forgets Something

If two subproblems with the same state can have different answers, the state is missing information. A memoized recursion then returns a cached answer that belongs to a different situation. The fix is to add the missing value to the state, or to change the problem definition.

Memory and Overflow

A table of n × m integers is 8·n·m bytes: 10,000 × 10,000 is 800 MB. Reduce to a rolling row once the full table works, and remember that walking back to recover choices needs the full table (or a stored choice). Counting DPs grow fast: the number of paths in a 40 × 40 grid no longer fits in 64 bits, so ask for the answer modulo a number if the problem allows it.

Practice Lab

For each exercise, write the state and its one-sentence meaning first. Then write the brute force, then the DP.

Run the Demos

1. In 50_memo_tabulation.go, replace max(prev1, prev2+v) by prev2+v in robber, so the current house is always robbed. Which check fails, and for what kind of loot?
2. In 51_knapsack_family.go, make the loop in knapsackRolling go upward (for w := it.weight; w <= capacity; w++). Which check fails, and which problem does the changed loop solve instead?
3. In 52_sequence_dp.go, remove d[i-1][j] from the min in editTable. Which operation can no longer be used, and which strings fail?
4. In 53_interval_partition_dp.go, replace the length loops in matrixChain by for i := 0; i < n; i++ and for j := i + 1; j < n; j++. Which cells are read before they are filled?
5. In 54_bitmask_state_dp.go, let newHold also come from sold - p. Which stock rule have you broken?

Exercises

1. Climbing stairs with forbidden steps. You climb 1 or 2 steps at a time and some steps are broken. Count the ways to reach the top, then shrink the table to two variables.
2. Maximum subarray. Find the contiguous subarray with the largest sum. Use the state "the best sum of a subarray that ends at i", and note how it relates to the house robber.
3. Longest palindromic substring. Use an interval table like isPal, and return the substring itself. Compare with expanding around each centre in O(n²) time and O(1) memory.
4. Unique paths with a budget. Cells have costs, and you may spend at most B in total. What must the state contain now? How large is the table?
5. Turn a recursion into a DP. Write the plain recursion for the number of ways to tile a 2 × n strip with 2 × 1 dominoes (laid either way). Count its calls, add a cache, then write the table.

Continue with Backtracking, for the problems where you must list solutions instead of counting them.