Go Guide

DP, math & design · Lesson 36 of 62 · about 60 min

Dynamic programming I

Stop solving the same subproblem twice: from slow recursion to memoization to a bottom-up table, with a recipe that works on every DP problem.

Visualgo: recursion tree and DP ↗
On this page · 12 sections
  1. 01The problem with naive recursion
  2. 02Fix 1: memoization (top-down)
  3. 03Fix 2: tabulation (bottom-up)
  4. 04The DP recipe
  5. 05Example: House Robber
  6. 06Example: Coin Change
  7. 07The full program
  8. 08Complexity
  9. 09Recognizing the pattern
  10. 10Summary
  11. 11Check your understanding
  12. 12Practice in Go

The problem with naive recursion#

Climbing stairs: you can climb 1 or 2 steps at a time; how many ways reach step n? To reach step n, your last move came from step n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2). Coded directly:

Go
func ways(n int) int {
	if n <= 1 {
		return 1
	}
	return ways(n-1) + ways(n-2)
}

The call tree for ways(5):

                    ways(5)
             /                \
        ways(4)               ways(3)
       /      \              /      \
   ways(3)   ways(2)     ways(2)   ways(1)
   /    \     /   \       /   \
ways(2) w(1) w(1) w(0)  w(1) w(0)
 /  \
w(1) w(0)

ways(3) is computed twice, ways(2) three times. The tree doubles at each level: O(2ⁿ). For n = 50 that is about a thousand trillion calls.

Fix 1: memoization (top-down)#

Keep the recursion, but cache results:

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

Each n is computed once: O(n).

Measure it

Count how many times each version calls itself. The naive count grows like the Fibonacci numbers themselves; the memoized count grows by 2 per step:

calls.go
Go
package main
 
import "fmt"
 
func main() {
	for _, n := range []int{10, 20, 30} {
		naiveCalls := 0
		var naive func(n int) int
		naive = func(n int) int {
			naiveCalls++
			if n <= 1 {
				return 1
			}
			return naive(n-1) + naive(n-2)
		}
 
		memoCalls := 0
		memo := map[int]int{}
		var fast func(n int) int
		fast = func(n int) int {
			memoCalls++
			if n <= 1 {
				return 1
			}
			if v, ok := memo[n]; ok {
				return v
			}
			memo[n] = fast(n-1) + fast(n-2)
			return memo[n]
		}
 
		a, b := naive(n), fast(n)
		fmt.Printf("n=%d ways=%d  naive calls=%-8d memo calls=%d  same=%v\n", n, a, naiveCalls, memoCalls, a == b)
	}
}
Output
n=10 ways=89  naive calls=177      memo calls=19  same=true
n=20 ways=10946  naive calls=21891    memo calls=39  same=true
n=30 ways=1346269  naive calls=2692537  memo calls=59  same=true

Fix 2: tabulation (bottom-up)#

Fill a table from the smallest subproblem up, so every value you need is already there:

i012345
ways[i]112358

Each entry only uses the two before it, so two variables replace the whole table: O(1) space.

Run it

The table version, then the same loop rolled into two variables:

tabulation.go
Go
package main
 
import "fmt"
 
func main() {
	n := 5
	ways := make([]int, n+1)
	ways[0], ways[1] = 1, 1
	for i := 2; i <= n; i++ {
		ways[i] = ways[i-1] + ways[i-2]
		fmt.Printf("ways[%d] = ways[%d] + ways[%d] = %d + %d = %d\n", i, i-1, i-2, ways[i-1], ways[i-2], ways[i])
	}
	fmt.Println("table:", ways)
 
	prev, cur := 1, 1 // ways[i-2], ways[i-1]
	for i := 2; i <= 50; i++ {
		prev, cur = cur, prev+cur
	}
	fmt.Println("ways(50) with O(1) memory:", cur)
}
Output
ways[2] = ways[1] + ways[0] = 1 + 1 = 2
ways[3] = ways[2] + ways[1] = 2 + 1 = 3
ways[4] = ways[3] + ways[2] = 3 + 2 = 5
ways[5] = ways[4] + ways[3] = 5 + 3 = 8
table: [1 1 2 3 5 8]
ways(50) with O(1) memory: 20365011074

The DP recipe#

Use these five steps on every DP problem. Write them down before coding.

  1. State: what does dp[i] mean, in one precise sentence? ("dp[i] = most money from the first i houses.")
  2. Transition: how is dp[i] computed from smaller states? Think about the last decision.
  3. Base cases: the smallest states, answered directly.
  4. Order: fill so dependencies come first (usually increasing i).
  5. Answer: which entry is the result? (Often dp[n].)

Example: House Robber#

Houses in a row hold money; you cannot rob two neighbors. Maximize the total.

  1. State: dp[i] = the best total using the first i houses.
  2. Transition, on the last decision (house i-1, zero-based): skip it, giving dp[i-1]; or rob it, giving dp[i-2] + nums[i-1]. Take the max.
  3. Base: dp[0] = 0, dp[1] = nums[0].
  4. Order: increasing i. 5. Answer: dp[n].

Trace nums = [2, 7, 9, 3, 1]:

ihouse valueskip: dp[i-1]rob: dp[i-2] + valuedp[i]
00
1200 + 22
2720 + 77
3972 + 911
43117 + 311
511111 + 112

Answer 12 (houses 2, 9 and 1).

Run the trace

The program fills the table from the trace above, then walks it backward to recover which houses were robbed: wherever dp[i] differs from dp[i-1], house i-1 was taken.

robber_trace.go
Go
package main
 
import "fmt"
 
func main() {
	nums := []int{2, 7, 9, 3, 1}
	dp := make([]int, len(nums)+1)
	dp[1] = nums[0]
	for i := 2; i <= len(nums); i++ {
		skip, rob := dp[i-1], dp[i-2]+nums[i-1]
		dp[i] = max(skip, rob)
		fmt.Printf("i=%d value=%d skip=%-2d rob=%-2d dp=%d\n", i, nums[i-1], skip, rob, dp[i])
	}
	fmt.Println("dp:", dp)
 
	var robbed []int
	for i := len(nums); i >= 1; {
		if dp[i] == dp[i-1] {
			i-- // house i-1 skipped
		} else {
			robbed = append([]int{nums[i-1]}, robbed...)
			i -= 2 // house i-1 robbed, so its neighbor was skipped
		}
	}
	fmt.Println("robbed:", robbed)
}
Output
i=2 value=7 skip=2  rob=7  dp=7
i=3 value=9 skip=7  rob=11 dp=11
i=4 value=3 skip=11 rob=10 dp=11
i=5 value=1 skip=11 rob=12 dp=12
dp: [0 2 7 11 11 12]
robbed: [2 9 1]

Example: Coin Change#

Fewest coins to make amount, coins reusable; -1 if impossible.

  1. State: dp[a] = fewest coins summing to a.
  2. Transition: the last coin used is some c, so dp[a] = min over c of dp[a-c] + 1.
  3. Base: dp[0] = 0. Everything else starts at "infinity" (impossible).

Trace coins = [1, 3, 4], amount = 6:

acandidates (via coin 1, 3, 4)dp[a]
00
1dp[0]+11
2dp[1]+12
3dp[2]+1, dp[0]+11
4dp[3]+1, dp[1]+1, dp[0]+11
5dp[4]+1, dp[2]+1, dp[1]+12
6dp[5]+1, dp[3]+1, dp[2]+12 (3 + 3)

A greedy "take the biggest coin" would pick 4 + 1 + 1 = 3 coins. DP considers every last coin and finds 2.

Run the trace

The program fills dp, records which coin achieved each best value, and compares the result with the greedy approach:

coins_trace.go
Go
package main
 
import (
	"fmt"
	"slices"
)
 
func main() {
	coins, amount := []int{1, 3, 4}, 6
	const inf = 1 << 30 // safe to add 1 to
	dp := make([]int, amount+1)
	last := make([]int, amount+1) // the coin used last in the best way to make a
	for a := 1; a <= amount; a++ {
		dp[a] = inf
		for _, c := range coins {
			if c <= a && dp[a-c]+1 < dp[a] {
				dp[a], last[a] = dp[a-c]+1, c
			}
		}
		fmt.Printf("dp[%d] = %d (last coin %d)\n", a, dp[a], last[a])
	}
 
	var used []int
	for a := amount; a > 0; a -= last[a] {
		used = append(used, last[a])
	}
	fmt.Println("DP uses", used)
 
	var greedy []int
	desc := slices.Clone(coins)
	slices.Reverse(desc)
	for a := amount; a > 0; {
		for _, c := range desc {
			if c <= a {
				greedy = append(greedy, c)
				a -= c
				break
			}
		}
	}
	fmt.Println("greedy uses", greedy)
}
Output
dp[1] = 1 (last coin 1)
dp[2] = 2 (last coin 1)
dp[3] = 1 (last coin 3)
dp[4] = 1 (last coin 4)
dp[5] = 2 (last coin 1)
dp[6] = 2 (last coin 3)
DP uses [3 3]
greedy uses [4 1 1]

Step through it

Try coins 2 5 with amount 3 (impossible), or 1 5 6 9 with amount 11, where greedy picks 9+1+1 but the answer is 5+6.

The full program#

dp1.go
Go
package main
 
import (
	"fmt"
	"math"
)
 
func climbStairs(n int) int {
	a, b := 1, 1 // ways to reach step i-1 and i
	for range n - 1 {
		a, b = b, a+b
	}
	return b
}
 
func climbMemo(n int) int {
	memo := map[int]int{}
	var ways func(int) int
	ways = func(i int) int {
		if i <= 1 {
			return 1
		}
		if v, ok := memo[i]; ok {
			return v
		}
		memo[i] = ways(i-1) + ways(i-2)
		return memo[i]
	}
	return ways(n)
}
 
func rob(nums []int) int {
	prev, cur := 0, 0 // dp[i-2], dp[i-1]
	for _, n := range nums {
		prev, cur = cur, max(cur, prev+n)
	}
	return cur
}
 
func coinChange(coins []int, amount int) int {
	const inf = math.MaxInt32 // large but safe to add 1 to
	dp := make([]int, amount+1)
	for a := 1; a <= amount; a++ {
		dp[a] = inf
		for _, c := range coins {
			if c <= a && dp[a-c] != inf {
				dp[a] = min(dp[a], dp[a-c]+1)
			}
		}
	}
	if dp[amount] == inf {
		return -1
	}
	return dp[amount]
}
 
func lengthOfLIS(nums []int) int {
	dp := make([]int, len(nums)) // dp[i] = longest increasing run ending at i
	best := 0
	for i := range nums {
		dp[i] = 1
		for j := range i {
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		best = max(best, dp[i])
	}
	return best
}
 
func wordBreak(s string, words []string) bool {
	dict := map[string]bool{}
	for _, w := range words {
		dict[w] = true
	}
	dp := make([]bool, len(s)+1) // dp[i]: s[:i] can be segmented
	dp[0] = true
	for i := 1; i <= len(s); i++ {
		for j := range i {
			if dp[j] && dict[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)]
}
 
func main() {
	fmt.Println(climbStairs(5), climbStairs(45), climbMemo(45))
	fmt.Println(rob([]int{2, 7, 9, 3, 1}))
	fmt.Println(coinChange([]int{1, 3, 4}, 6), coinChange([]int{2}, 3), coinChange([]int{1}, 0))
	fmt.Println(lengthOfLIS([]int{10, 9, 2, 5, 3, 7, 101, 18}))
	fmt.Println(wordBreak("gopherpath", []string{"go", "pher", "path"}), wordBreak("gopath", []string{"gop", "path"}))
}
Output
8 1836311903 1836311903
12
2 -1 0
4
true false

Complexity#

ProblemTimeSpace
climbing stairsO(n)O(1)
house robberO(n)O(1)
coin changeO(amount · coins)O(amount)
LIS (simple)O(n²)O(n)
word breakO(n²) substring checksO(n)

Recognizing the pattern#

"Number of ways", "minimum / maximum cost", "is it possible", combined with choices at each step where the future depends only on where you are (not how you got there). If you write a recursive solution and see the same arguments repeat, it is DP.

Summary#

  • DP = recursion that remembers: solve each subproblem once.
  • Memoization (top-down) adds a cache to recursion; tabulation (bottom-up) fills a table with loops.
  • Recipe: state, transition (on the last decision), base cases, order, answer.
  • When a state depends only on the last one or two, roll the table into variables.
  • Use a safe infinity for "impossible" in min problems.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.What two properties make a problem suitable for dynamic programming?

  2. Q2.Plain recursive Fibonacci is O(2ⁿ). With memoization it becomes:

  3. Q3.In House Robber, cur = max(cur, prev+n) means:

  4. Q4.In Coin Change, why initialize dp entries to a large 'infinity' instead of 0?

  5. Q5.Top-down vs bottom-up DP:

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

  • Climbing Stairs ↗easy
    Show hint

    ways(i) = ways(i-1) + ways(i-2). Two variables are enough.

  • Min Cost Climbing Stairs ↗easy
    Show hint

    dp[i] = cost[i] + min(dp[i-1], dp[i-2]); the answer is the min of the last two.

  • House Robber ↗medium
    Show hint

    Track best-including-up-to-i-2 and best-up-to-i-1.

  • Coin Change ↗medium
    Show hint

    dp[a] = min over coins of dp[a-coin] + 1; dp[0] = 0.

  • Longest Increasing Subsequence ↗medium
    Show hint

    O(n²): dp[i] = 1 + max dp[j] for j < i with nums[j] < nums[i]. O(n log n) uses binary search on tails.

  • Word Break ↗medium
    Show hint

    dp[i] is true if some dp[j] is true and s[j:i] is a dictionary word.

  • Decode Ways ↗medium
    Show hint

    Like climbing stairs, but a step of 1 or 2 digits is allowed only if it forms a valid letter code.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.