Dynamic Programming

What makes a problem a DP problem

Dynamic programming applies when a problem has two properties at once:

• Overlapping subproblems — the same smaller problem shows up many times. Solve it once, cache the answer, and every later occurrence is a free lookup.
• Optimal substructure — an optimal solution to the whole is built from optimal solutions to its parts. That lets you combine subproblem answers instead of searching the entire space.

When both hold, you get the classic progression: naive recursion re-solves subproblems and explodes (often O(2ⁿ)), then memoization (top-down) caches results, then tabulation (bottom-up) fills a table in dependency order. The last two are usually O(n) or O(n·m).

graph TD
F5["fib(5)"] --> F4["fib(4)"]
F5 --> F3a["fib(3)"]
F4 --> F3b["fib(3)"]
F4 --> F2a["fib(2)"]
F3a --> F2b["fib(2)"]
F3a --> F1a["fib(1)"]
F3b --> F2c["fib(2)"]
F3b --> F1b["fib(1)"]
classDef dup fill:#2a0f17,stroke:#f43f5e,color:#ffd7e0;
class F3b,F2a,F2b,F2c,F1a,F1b dup;

The red nodes are recomputed work — fib(3) and fib(2) appear again and again. That repetition is exactly what memoization erases.

Fibonacci three ways

fib(n) = fib(n-1) + fib(n-2) is the canonical example because the naive version visibly re-solves the same calls. The playground below runs all three approaches and counts how many times each actually calls into fib, so you can see the O(2ⁿ) → O(n) collapse directly:

package main

import "fmt"

// 1) Naive recursion: re-solves overlapping subproblems. O(2^n).
var naiveCalls int

func fibNaive(n int) int {
naiveCalls++
if n < 2 {
	return n
}
return fibNaive(n-1) + fibNaive(n-2)
}

// 2) Top-down memoization: cache each result, compute it once. O(n).
var memoCalls int

func fibMemo(n int, cache []int) int {
memoCalls++
if n < 2 {
	return n
}
if cache[n] != -1 {
	return cache[n] // already solved
}
cache[n] = fibMemo(n-1, cache) + fibMemo(n-2, cache)
return cache[n]
}

// 3) Bottom-up tabulation: fill a table in order, no recursion. O(n) time, O(1) space.
func fibTab(n int) int {
if n < 2 {
	return n
}
prev, curr := 0, 1
for i := 2; i <= n; i++ {
	prev, curr = curr, prev+curr
}
return curr
}

func main() {
const n = 30

naiveValue := fibNaive(n)

cache := make([]int, n+1)
for i := range cache {
	cache[i] = -1
}
memoValue := fibMemo(n, cache)

tabValue := fibTab(n)

fmt.Printf("fib(%d) = %d (all three agree: %v)\n",
	n, naiveValue, naiveValue == memoValue && memoValue == tabValue)
fmt.Printf("naive calls: %d  (exponential)\n", naiveCalls)
fmt.Printf("memo  calls: %d  (linear)\n", memoCalls)
}

The call counts tell the whole story: naive makes over two million calls for fib(30), while memoization makes about sixty. Same answer, wildly different cost.

A second classic: coin change (minimum coins)

Fibonacci shows the mechanics; coin change shows the power. Given coin denominations and a target amount, find the fewest coins that sum to it. The subproblem is “min coins for amount a”, and it overlaps heavily — many amounts depend on the same smaller amounts.

Bottom-up, dp[a] = minimum coins to make amount a. Start with dp[0] = 0 and build up: for each amount, try every coin and take the best.

graph LR
A0["dp[0]=0"] --> A1["dp[1]"]
A1 --> A2["dp[2]"]
A2 --> A3["dp[3]"]
A3 --> A4["dp[4]"]
A4 --> A5["dp[5]"]
A5 --> A6["dp[6]=min over coins"]

package main

import "fmt"

// minCoins returns the fewest coins summing to amount, or -1 if impossible.
// Bottom-up DP: dp[a] = min coins for amount a. Time O(amount * len(coins)).
func minCoins(coins []int, amount int) int {
const unreachable = 1 << 30
dp := make([]int, amount+1)
for a := 1; a <= amount; a++ {
	dp[a] = unreachable
}
// dp[0] stays 0: zero coins make amount 0.

for a := 1; a <= amount; a++ {
	for _, c := range coins {
		if c <= a && dp[a-c]+1 < dp[a] {
			dp[a] = dp[a-c] + 1
		}
	}
}

if dp[amount] >= unreachable {
	return -1
}
return dp[amount]
}

func main() {
coins := []int{1, 3, 4}
amount := 6

n := minCoins(coins, amount)
fmt.Printf("coins %v, amount %d -> %d coins (DP, exact)\n", coins, amount, n)
// DP finds 3+3 = 2 coins. A greedy 4+1+1 would use 3.

// Impossible case: no combination of {2} reaches an odd amount.
fmt.Printf("coins %v, amount %d -> %d\n", []int{2}, 3, minCoins([]int{2}, 3))
}

For coins [1, 3, 4] and amount 6, DP returns 2 (3 + 3). A greedy “take the largest coin that fits” would grab 4, then 1 + 1, for 3 coins — wrong. DP is exact because it considers every coin for every amount instead of committing early. That contrast with greedy algorithms is the key takeaway: greedy is faster but only correct for special coin systems; DP always finds the true minimum.

See also

• recursion & backtracking — the exponential starting point DP optimizes.
• greedy — faster, but only correct when local choices are globally optimal.
• Big-O — the O(2ⁿ) → O(n) collapse memoization buys.
• union-find — the structure behind Kruskal, a greedy cousin of DP problems.

Next: when the locally optimal choice is enough — greedy algorithms.

Related topics