Dynamic programming II

Two-dimensional states for grids and pairs of strings, the 0/1 knapsack, and shrinking tables to one row.

Grids: Unique Paths#

A robot starts top-left and moves only right or down. How many paths reach the bottom-right of an m × n grid?

State: dp[r][c] = number of paths to cell (r, c).
Transition: the last move came from above or from the left: dp[r][c] = dp[r-1][c] + dp[r][c-1].
Base: the first row and column are all 1 (only one way along an edge).

For a 3 × 4 grid:

	c0	c1	c2	c3
r0	1	1	1	1
r1	1	2	3	4
r2	1	3	6	10

Shrinking to one row: each row needs only the row above and the cell to its left, so keep one row and update it in place: row[c] += row[c-1]. Before the update row[c] holds the value from above; row[c-1] was already updated, so it holds the value from the left.

Run it

The full table, then the one-row version producing the same answer:

paths.go

package main
 
import "fmt"
 
func main() {
	m, n := 3, 4
	dp := make([][]int, m)
	for r := range dp {
		dp[r] = make([]int, n)
		for c := range dp[r] {
			if r == 0 || c == 0 {
				dp[r][c] = 1 // edges: one way
			} else {
				dp[r][c] = dp[r-1][c] + dp[r][c-1] // from above + from the left
			}
		}
		fmt.Println(dp[r])
	}
 
	row := make([]int, n)
	for c := range row {
		row[c] = 1
	}
	for r := 1; r < m; r++ {
		for c := 1; c < n; c++ {
			row[c] += row[c-1]
		}
		fmt.Println("one row after r =", r, row)
	}
}

Output

[1 1 1 1]
[1 2 3 4]
[1 3 6 10]
one row after r = 1 [1 2 3 4]
one row after r = 2 [1 3 6 10]

Two strings: Longest Common Subsequence#

A subsequence keeps order but may skip characters: "ace" is a subsequence of "abcde". LCS asks for the longest one shared by two strings.

State: dp[i][j] = LCS length of a[:i] and b[:j]. Row 0 and column 0 represent empty prefixes, so they are 0.
Transition, on the last characters:
- if a[i-1] == b[j-1], they can both end the LCS: dp[i-1][j-1] + 1 (diagonal);
- otherwise drop one of them: max(dp[i-1][j], dp[i][j-1]) (up or left).

a = "abcde", b = "ace":

	a	c	e
""	0	0	0
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

Bold cells are matches (diagonal + 1). The answer, bottom-right, is 3.

Run it

The program prints the same table as above, then walks back from the bottom-right corner to recover the subsequence itself: a match means go diagonal and keep the character; otherwise move toward the larger neighbor.

lcs_table.go

package main
 
import (
	"fmt"
	"strings"
)
 
func main() {
	a, b := "abcde", "ace"
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
 
	fmt.Println("       " + strings.Join(strings.Split(b, ""), " "))
	for i, row := range dp {
		label := "\"\""
		if i > 0 {
			label = " " + a[i-1:i]
		}
		fmt.Printf("%-3s %v\n", label, row)
	}
 
	var out []byte
	for i, j := len(a), len(b); i > 0 && j > 0; {
		switch {
		case a[i-1] == b[j-1]:
			out = append([]byte{a[i-1]}, out...)
			i, j = i-1, j-1
		case dp[i-1][j] >= dp[i][j-1]:
			i--
		default:
			j--
		}
	}
	fmt.Printf("LCS = %q (length %d)\n", out, dp[len(a)][len(b)])
}

Output

       a c e
""  [0 0 0 0]
 a  [0 1 1 1]
 b  [0 1 1 1]
 c  [0 1 2 2]
 d  [0 1 2 2]
 e  [0 1 2 3]
LCS = "ace" (length 3)

Step through it

InteractiveLongest common subsequencedp[i][j] is the LCS of the first i letters of A and the first j of B. A match goes diagonal + 1; otherwise take the better of up and left.

	b	d	c	a	b	a
∅	0	0	0	0	0	0
a
b
c
b
d
a
b

Row 0 and column 0 are empty prefixes: their LCS is 0.

1 / 44

Edit Distance#

The minimum number of single-character inserts, deletes and replacements turning a into b. It is the engine of spell checkers and diff. Same table shape:

Last step	Cell it comes from	Cost
characters equal	diagonal `dp[i-1][j-1]`	0
replace `a[i-1]` with `b[j-1]`	diagonal	+1
delete `a[i-1]`	up `dp[i-1][j]`	+1
insert `b[j-1]`	left `dp[i][j-1]`	+1

Base: turning a prefix of length i into the empty string takes i deletes (column 0 = i), and building a prefix of length j from empty takes j inserts (row 0 = j).

Run it

horse to ros is the classic example. The program prints the table and then the actual edits, found by walking back through the cells that produced each value:

edit_trace.go

package main
 
import "fmt"
 
func main() {
	a, b := "horse", "ros"
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
		dp[i][0] = i // delete everything
	}
	for j := range dp[0] {
		dp[0][j] = j // insert everything
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[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])
			}
		}
	}
	for _, row := range dp {
		fmt.Println(row)
	}
 
	var steps []string
	for i, j := len(a), len(b); i > 0 || j > 0; {
		switch {
		case i > 0 && j > 0 && a[i-1] == b[j-1]:
			i, j = i-1, j-1
		case i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1]+1:
			steps = append([]string{fmt.Sprintf("replace %c with %c", a[i-1], b[j-1])}, steps...)
			i, j = i-1, j-1
		case i > 0 && dp[i][j] == dp[i-1][j]+1:
			steps = append([]string{fmt.Sprintf("delete %c", a[i-1])}, steps...)
			i--
		default:
			steps = append([]string{fmt.Sprintf("insert %c", b[j-1])}, steps...)
			j--
		}
	}
	fmt.Println("distance:", dp[len(a)][len(b)])
	for _, s := range steps {
		fmt.Println(" ", s)
	}
}

Output

[0 1 2 3]
[1 1 2 3]
[2 2 1 2]
[3 2 2 2]
[4 3 3 2]
[5 4 4 3]
distance: 3
  replace h with r
  delete r
  delete e

0/1 Knapsack#

Items have weights; each can be used once. Can you pick a subset hitting an exact target (or maximize value within a capacity)? "Partition Equal Subset Sum" asks whether some subset sums to half the total.

State: can[s] = some subset of the items seen so far sums to s.
For each item n, for each s: can[s] = can[s] || can[s-n].
Loop s downward. Going upward, can[s-n] might already include item n, using it twice.

Trace nums = [1, 5, 11, 5], target 11 (only showing which sums are reachable):

after item	reachable sums
(start)	0
1	0, 1
5	0, 1, 5, 6
11	0, 1, 5, 6, 11
5	0, 1, 5, 6, 10, 11

11 is reachable, so the array splits into [11] and [1, 5, 5].

Run the trace, and the upward-loop bug

The correct downward loop reproduces the table above. Looping upward lets one item be used again within the same pass, so with the single item 5, the upward version wrongly claims 10 and 15 are reachable:

knapsack_trace.go

package main
 
import "fmt"
 
func reachable(can []bool) []int {
	var out []int
	for s, ok := range can {
		if ok {
			out = append(out, s)
		}
	}
	return out
}
 
func main() {
	nums, target := []int{1, 5, 11, 5}, 11
	can := make([]bool, target+1)
	can[0] = true
	for _, n := range nums {
		for s := target; s >= n; s-- { // downward: each item once
			can[s] = can[s] || can[s-n]
		}
		fmt.Printf("after %2d: %v\n", n, reachable(can))
	}
	fmt.Println("can make", target, "=", can[target])
 
	bad := make([]bool, 16)
	bad[0] = true
	for s := 5; s < len(bad); s++ { // upward with the single item 5
		bad[s] = bad[s] || bad[s-5]
	}
	fmt.Println("upward with one 5:", reachable(bad))
}

Output

after  1: [0 1]
after  5: [0 1 5 6]
after 11: [0 1 5 6 11]
after  5: [0 1 5 6 10 11]
can make 11 = true
upward with one 5: [0 5 10 15]

The full program#

dp2.go

package main
 
import "fmt"
 
func uniquePaths(m, n int) int {
	row := make([]int, n)
	for c := range row {
		row[c] = 1
	}
	for range m - 1 {
		for c := 1; c < n; c++ {
			row[c] += row[c-1] // above + left
		}
	}
	return row[n-1]
}
 
func lcs(a, b string) int {
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[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(a)][len(b)]
}
 
func editDistance(a, b string) int {
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
		dp[i][0] = i // delete everything
	}
	for j := range dp[0] {
		dp[0][j] = j // insert everything
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[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(a)][len(b)]
}
 
func canPartition(nums []int) bool {
	total := 0
	for _, n := range nums {
		total += n
	}
	if total%2 == 1 {
		return false
	}
	target := total / 2
	can := make([]bool, target+1)
	can[0] = true
	for _, n := range nums {
		for s := target; s >= n; s-- { // downward: each item once
			can[s] = can[s] || can[s-n]
		}
	}
	return can[target]
}
 
func longestPalindrome(s string) string {
	start, length := 0, 0
	expand := func(l, r int) {
		for l >= 0 && r < len(s) && s[l] == s[r] {
			l--
			r++
		}
		if r-l-1 > length {
			start, length = l+1, r-l-1
		}
	}
	for i := range len(s) {
		expand(i, i)   // odd length, centered on i
		expand(i, i+1) // even length, centered between i and i+1
	}
	return s[start : start+length]
}
 
func main() {
	fmt.Println(uniquePaths(3, 4), uniquePaths(3, 7))
	fmt.Println(lcs("abcde", "ace"), lcs("abc", "def"))
	fmt.Println(editDistance("horse", "ros"), editDistance("kitten", "sitting"))
	fmt.Println(canPartition([]int{1, 5, 11, 5}), canPartition([]int{1, 2, 3, 5}))
	fmt.Println(longestPalindrome("babad"), longestPalindrome("cbbd"))
}

Output

10 28
3 0
3 3
true false
bab bb

Complexity#

Problem	Time	Space
unique paths	O(m · n)	O(n)
LCS, edit distance	O(len(a) · len(b))	O(len(a) · len(b)), reducible to two rows
partition (0/1 knapsack)	O(n · target)	O(target)
longest palindromic substring (expand)	O(n²)	O(1)

Recognizing the pattern#

A grid with moves only right/down (or similar): dp[r][c].
Two strings or sequences compared: dp[i][j] over prefixes.
Choose a subset under a budget, each item once: knapsack; loop capacity downward.
Intervals of one string (palindromes, burst balloons): dp[i][j] over substrings, filled by increasing length.

Summary#

Use two indexes when one cannot describe the subproblem: grid cells or prefix pairs.
Add an empty row and column for empty prefixes to remove edge cases.
Match → diagonal; otherwise combine up and left.
0/1 knapsack with one row loops capacity downward so each item is used once.
Shrink to one or two rows when each row depends only on the previous one.

Dynamic programming II

Grids: Unique Paths#

Run it

Two strings: Longest Common Subsequence#

Run it

Step through it

Edit Distance#

Run it

0/1 Knapsack#

Run the trace, and the upward-loop bug

The full program#

Complexity#

Recognizing the pattern#

Summary#

Check your understanding

Practice in Go