Dev Skills
Go·Go for coding rounds

Dynamic programming: stairs, coins, LCS

Write the answer for a small case in terms of smaller ones, then fill a table from the bottom up.

Topic 35 of 98 · 10 min to read · 45 min to build
After this topic you can
  • Write the recurrence for stairs, coin change and LCS before coding.
  • Fill a small DP table by hand and check it against the program.
  • Explain why plain recursion is exponential and DP is not.

The problem

Three classics. Climbing stairs: how many ways to climb n steps taking 1 or 2 at a time. Coin change: the fewest coins that make an amount, or -1. Longest common subsequence: the length of the longest sequence of characters that appears, in order, in both strings.

Brute force first

Plain recursion straight from the recurrence. For stairs: ways(n) = ways(n-1) + ways(n-2). It is correct, but ways(3) is recomputed again and again: O(2ⁿ) time, O(n) stack. Coin change and LCS blow up the same way.

DP is this same recursion with each answer stored once and filled from small to large.

The approach

Find the recurrence first. Stairs: ways(n) = ways(n-1) + ways(n-2). Coins: best(x) = 1 + min(best(x-c)) over each coin c. LCS: if the last characters match, 1 + lcs(shorter both), else the larger of dropping one from either side.

Then fill the answers from small to large so each one is ready when you need it. Stairs is O(n) time, O(1) space. Coins is O(amount · coins). LCS is O(n · m) time and space.

stairs_recursive.go
package main
import "fmt"
var calls int
// The brute force: correct, but exponential. Each call makes two more.
func ways(n int) int {
	calls++
	if n <= 1 {
		return 1
	}
	return ways(n-1) + ways(n-2)
}
func main() {
	fmt.Println(ways(25), "calls:", calls) // 121393 calls: 242785
}

Problem 1: climbing stairs

Recurrence: ways(n) = ways(n-1) + ways(n-2), with ways(0) = ways(1) = 1. To stand on step n, your last move came from step n-1 (a 1-step) or n-2 (a 2-step).

Table trace for n = 5, filled left to right:

step i012345
ways(i)112358
stairs.go
package main
import "fmt"
// ways(n) = ways(n-1) + ways(n-2), ways(0) = ways(1) = 1.
// Only the last two answers are needed, so keep two variables.
func climbStairs(n int) int {
	a, b := 1, 1 // ways to reach step 0 and step 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}
func main() {
	fmt.Println(climbStairs(2), climbStairs(5), climbStairs(10)) // 2 8 89
}

Problem 2: coin change

Recurrence: best(0) = 0, and best(x) = 1 + min(best(x - c)) over every coin c <= x. If nothing works, it stays "infinity" and the answer is -1.

Table trace for coins [1 2 5], amount 6:

amount x0123456
best(x)0112212
from-0+10+21+22+20+51+5
coins.go
package main
import "fmt"
// best[x] = 1 + min(best[x-c]) over each coin c <= x, best[0] = 0.
func coinChange(coins []int, amount int) int {
	const inf = 1 << 30 // safe "infinity": inf + 1 cannot overflow
	best := make([]int, amount+1)
	for x := 1; x <= amount; x++ {
		best[x] = inf
		for _, c := range coins {
			if c <= x && best[x-c]+1 < best[x] {
				best[x] = best[x-c] + 1
			}
		}
	}
	if best[amount] >= inf {
		return -1
	}
	return best[amount]
}
func main() {
	fmt.Println(coinChange([]int{1, 2, 5}, 6))  // 2 (5+1)
	fmt.Println(coinChange([]int{1, 2, 5}, 11)) // 3 (5+5+1)
	fmt.Println(coinChange([]int{2}, 3))        // -1
}

Problem 3: longest common subsequence

Recurrence: dp[i][j] is the LCS of the first i characters of a and the first j of b. If a[i-1] == b[j-1], dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Row 0 and column 0 are 0.

Table trace for a = "abcde", b = "ace". The answer is the bottom-right cell:

""ace
""0000
a0111
b0111
c0122
d0122
e0123
lcs.go
package main
import "fmt"
// dp[i][j] = LCS of the first i runes of a and the first j runes of b.
// Match: dp[i-1][j-1] + 1. No match: max(dp[i-1][j], dp[i][j-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) // each row needs its own make
	}
	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 main() {
	fmt.Println(lcs("abcde", "ace")) // 3
	fmt.Println(lcs("abc", "def"))   // 0
}

Go-specific gotchas

  • A 2-D table needs a `make` per row. make([][]int, n) gives you n nil rows; writing to dp[i][j] then panics.
  • Pick a safe "infinity". 1 << 30 plus one cannot overflow. math.MaxInt + 1 wraps to a negative number and silently wins every min.
  • Use runes for strings if the input can contain non-ASCII text. a[i] is a byte, and comparing bytes of a multi-byte character gives wrong answers.
  • When only the last one or two rows matter, keep just those. Stairs needs two variables, not a slice.
The short version
  • Recurrence first, code second.
  • Fill from the smallest case up.
  • One make per row of a 2-D slice.
Remember: If plain recursion recomputes the same small cases again and again, store them. That is all DP is.
Build this before moving on
Solve "house robber": the most money from a row of houses when you cannot rob two next to each other. Write the recurrence before the code.
Coding challenge · checked by tests
Online-assessment style coin change. Write Solve(r io.Reader, w io.Writer). The input is T, then T cases; each case is n amount followed by n coin values. For each case print the fewest coins that make amount (unlimited coins of each value), or -1 if it cannot be made. Amounts go up to 10,000, so plain recursion is too slow: build the table bottom-up. Example: "1\n3 11\n1 2 5\n" → "3\n".

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Solve "house robber": the most money from a row of houses when you cannot rob two next to each other. Write the recurrence before the code.
  2. 2Fill the stairs table for n = 6 and check it against the program (climbStairs(5) is 8).
  3. 3Fill the best table for coins [1 3 4] and amount 6. Why is the greedy answer (take the biggest coin first) wrong here?
Official documentation
Check yourselfTake the Go for coding rounds test