Dynamic programming III

Longest increasing subsequence in O(n log n) with patience sorting, Word Break with DP and a trie, interval DP, DP on trees, and bitmask DP over subsets.

Longest increasing subsequence#

"Find the length of the longest strictly increasing subsequence" (not necessarily contiguous). For [10, 9, 2, 5, 3, 7, 101, 18] it is 4, for example [2, 3, 7, 18].

The O(n²) DP

State: dp[i] = length of the longest increasing subsequence ending at i. Transition: look at every earlier j with nums[j] < nums[i] and extend the best one: dp[i] = 1 + max(dp[j]). Answer: the maximum over all dp[i].

O(n log n) with patience sorting

Keep tails[k] = the smallest last value of any increasing subsequence of length k+1 seen so far. tails is always sorted, so for each new value, binary search for the first tail >= it:

if it is bigger than every tail, it extends the longest subsequence: append;
otherwise it replaces that tail with a smaller one, which makes future extensions easier.

The name comes from the card game patience: deal each card onto the leftmost pile whose top card is not smaller; the number of piles is the LIS length.

InteractiveLongest increasing subsequence (patience sorting)tails[k] is the smallest possible last value of an increasing subsequence of length k+1. Binary search where each number goes.

nums

010

6101

718

919

tails

010

10 is bigger than every tail: it extends the longest subsequence. Length is now 1.

1 / 11

lis.go

package main
 
import (
	"fmt"
	"slices"
	"sort"
)
 
func lisQuadratic(nums []int) int {
	dp := make([]int, len(nums))
	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
}
 
// lisFast returns the length and one actual longest subsequence.
func lisFast(nums []int) (int, []int) {
	var tails []int   // tails[k] = smallest tail value of a length-(k+1) subsequence
	var tailIdx []int // the index in nums of that tail
	prev := make([]int, len(nums))
	for i, x := range nums {
		k := sort.SearchInts(tails, x) // first tail >= x (strictly increasing)
		if k == len(tails) {
			tails = append(tails, x)
			tailIdx = append(tailIdx, i)
		} else {
			tails[k], tailIdx[k] = x, i
		}
		prev[i] = -1
		if k > 0 {
			prev[i] = tailIdx[k-1] // x extends the subsequence that ended at tailIdx[k-1]
		}
	}
	var seq []int
	for i := tailIdx[len(tailIdx)-1]; i != -1; i = prev[i] {
		seq = append(seq, nums[i])
	}
	slices.Reverse(seq)
	return len(tails), seq
}
 
func main() {
	nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
	n, seq := lisFast(nums)
	fmt.Println(lisQuadratic(nums), n, seq)
 
	// Russian dolls: sort by width up, height DOWN, then LIS on heights.
	env := [][2]int{{5, 4}, {6, 4}, {6, 7}, {2, 3}}
	slices.SortFunc(env, func(a, b [2]int) int {
		if a[0] != b[0] {
			return a[0] - b[0]
		}
		return b[1] - a[1] // same width can't nest: descending heights block that
	})
	heights := make([]int, len(env))
	for i, e := range env {
		heights[i] = e[1]
	}
	dolls, _ := lisFast(heights)
	fmt.Println("envelopes:", env, "max nesting:", dolls)
}

Output

4 4 [2 3 7 18]
envelopes: [[2 3] [5 4] [6 7] [6 4]] max nesting: 3

Recovering the actual subsequence needs one more array: prev[i] remembers which element nums[i] extended. (Comparator subtraction is fine here because widths and heights are small positive numbers; use cmp.Compare in general.)

Word Break: DP plus a trie#

"Can s be split into words from a dictionary?" State: dp[i] = the prefix s[:i] can be split. Base: dp[0] = true (the empty prefix). Transition: dp[i] is true if some j < i has dp[j] true and s[j:i] is a word.

Checking every j and building every substring s[j:i] costs O(n²) substrings, each hashed in O(n). A trie removes that waste: from each position j where dp[j] is true, walk the trie along s[j], s[j+1], …; every node marked as a word end at position i sets dp[i] = true, and the walk stops as soon as no dictionary word continues.

wordbreak.go

package main
 
import "fmt"
 
type Trie struct {
	next [26]*Trie
	end  bool
}
 
func (t *Trie) Add(w string) {
	for i := 0; i < len(w); i++ {
		c := w[i] - 'a'
		if t.next[c] == nil {
			t.next[c] = &Trie{}
		}
		t = t.next[c]
	}
	t.end = true
}
 
func wordBreak(s string, dict []string) (bool, []string) {
	root := &Trie{}
	for _, w := range dict {
		root.Add(w)
	}
	n := len(s)
	ok := make([]bool, n+1)
	from := make([]int, n+1) // from[i] = start of the last word in one valid split of s[:i]
	ok[0] = true
	for j := 0; j < n; j++ {
		if !ok[j] {
			continue
		}
		node := root
		for i := j; i < n; i++ {
			node = node.next[s[i]-'a']
			if node == nil {
				break // no dictionary word continues this way
			}
			if node.end && !ok[i+1] {
				ok[i+1], from[i+1] = true, j
			}
		}
	}
	if !ok[n] {
		return false, nil
	}
	var words []string
	for i := n; i > 0; i = from[i] {
		words = append([]string{s[from[i]:i]}, words...)
	}
	return true, words
}
 
func main() {
	fmt.Println(wordBreak("applepenapple", []string{"apple", "pen"}))
	fmt.Println(wordBreak("catsandog", []string{"cats", "dog", "sand", "and", "cat"}))
	fmt.Println(wordBreak("gophersgonnago", []string{"go", "gopher", "gophers", "gonna"}))
}

Output

true [apple pen apple]
false []
true [gophers gonna go]

Interval DP#

Some problems are about a range [i, j] and how to split it. State: dp[i][j] = the best answer for the subarray or substring from i to j. Transition: try every split point k inside, combining dp[i][k] and dp[k+1][j] (or, in some problems, choose the element that happens last). Order: by increasing length, so every smaller interval is ready.

Burst Balloons: bursting balloon k earns nums[left] · nums[k] · nums[right] with its current neighbors. Thinking about which balloon to burst first is hopeless because neighbors keep changing. Think about which balloon in (i, j) bursts last: at that moment its neighbors are exactly i and j, and the two sides are independent subproblems.

Longest palindromic subsequence uses the same table: if the ends match, 2 + dp[i+1][j-1]; otherwise drop one end.

interval.go

package main
 
import "fmt"
 
func maxCoins(nums []int) int {
	a := append(append([]int{1}, nums...), 1) // pad with virtual 1s at both ends
	n := len(a)
	dp := make([][]int, n) // dp[i][j] = best coins from bursting everything strictly between i and j
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for length := 2; length < n; length++ {
		for i := 0; i+length < n; i++ {
			j := i + length
			for k := i + 1; k < j; k++ { // k is the LAST balloon burst between i and j
				dp[i][j] = max(dp[i][j], dp[i][k]+a[i]*a[k]*a[j]+dp[k][j])
			}
		}
	}
	return dp[0][n-1]
}
 
func longestPalSubseq(s string) int {
	n := len(s)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][i] = 1
	}
	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			if s[i] == s[j] {
				dp[i][j] = 2 + dp[i+1][j-1]
			} else {
				dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			}
		}
	}
	return dp[0][n-1]
}
 
func main() {
	fmt.Println("burst balloons [3 1 5 8]:", maxCoins([]int{3, 1, 5, 8}))
	fmt.Println("longest palindromic subsequence of \"bbbab\":", longestPalSubseq("bbbab"))
}

Output

burst balloons [3 1 5 8]: 167
longest palindromic subsequence of "bbbab": 4

167 comes from bursting 1, then 5, then 3, then 8: 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 15 + 120 + 24 + 8.

DP on trees#

On a tree, the subproblems are subtrees, and the natural order is post-order: solve the children, then the node. Often each node returns a small tuple.

House Robber III: houses form a binary tree; you cannot rob a node and its parent. Each node returns (rob, skip): the best total for its subtree if it is robbed and if it is not. If robbed, its children must be skipped; if skipped, each child contributes its better option.

Diameter / maximum path sum: return the best path going down from the node, while updating a global answer with the best path through the node (left down + node + right down).

treedp.go

package main
 
import "fmt"
 
type Node struct {
	Val         int
	Left, Right *Node
}
 
func rob(n *Node) (robbed, skipped int) {
	if n == nil {
		return 0, 0
	}
	lr, ls := rob(n.Left)
	rr, rs := rob(n.Right)
	robbed = n.Val + ls + rs            // children must be skipped
	skipped = max(lr, ls) + max(rr, rs) // children are free to choose
	return robbed, skipped
}
 
func maxPathSum(root *Node) int {
	best := root.Val
	var down func(n *Node) int
	down = func(n *Node) int {
		if n == nil {
			return 0
		}
		l := max(0, down(n.Left)) // a negative branch is better left out
		r := max(0, down(n.Right))
		best = max(best, l+n.Val+r) // the best path that bends at n
		return n.Val + max(l, r)    // a path continuing upward can use only one side
	}
	down(root)
	return best
}
 
func main() {
	//      3
	//     / \
	//    2   3
	//     \   \
	//      3   1
	t := &Node{3, &Node{2, nil, &Node{Val: 3}}, &Node{3, nil, &Node{Val: 1}}}
	r, s := rob(t)
	fmt.Printf("house robber III: %d (rob root: %d, skip root: %d)\n", max(r, s), r, s)
 
	//    -10
	//    /  \
	//   9    20
	//       /  \
	//      15   7
	p := &Node{-10, &Node{Val: 9}, &Node{20, &Node{Val: 15}, &Node{Val: 7}}}
	fmt.Println("max path sum:", maxPathSum(p))
}

Output

house robber III: 7 (rob root: 7, skip root: 6)
max path sum: 42

Bitmask DP: subsets as integers#

When n is at most about 20, a set of items fits in an integer: bit i is 1 if item i is in the set. A DP over all 2ⁿ masks becomes possible. The classic is the traveling salesman problem: visit every city once and return home, as cheaply as possible.

State: dp[mask][v] = the cheapest way to start at city 0, visit exactly the cities in mask, and end at v. Transition: extend to an unvisited city u: dp[mask | 1<<u][u] = min(…, dp[mask][v] + dist[v][u]). That is O(2ⁿ · n²) instead of the O(n!) of trying every order: for n = 15, about 7 million steps instead of 1.3 trillion.

tsp.go

package main
 
import (
	"fmt"
	"math"
)
 
func tsp(dist [][]int) int {
	n := len(dist)
	full := 1<<n - 1
	dp := make([][]int, 1<<n)
	for m := range dp {
		dp[m] = make([]int, n)
		for v := range dp[m] {
			dp[m][v] = math.MaxInt / 2
		}
	}
	dp[1][0] = 0 // only city 0 visited, standing at city 0
	for mask := 1; mask <= full; mask++ {
		for v := range n {
			if mask&(1<<v) == 0 || dp[mask][v] >= math.MaxInt/2 {
				continue
			}
			for u := range n {
				if mask&(1<<u) != 0 {
					continue // already visited
				}
				next := mask | 1<<u
				dp[next][u] = min(dp[next][u], dp[mask][v]+dist[v][u])
			}
		}
	}
	best := math.MaxInt
	for v := 1; v < n; v++ {
		best = min(best, dp[full][v]+dist[v][0]) // return home
	}
	return best
}
 
func main() {
	dist := [][]int{
		{0, 10, 15, 20},
		{10, 0, 35, 25},
		{15, 35, 0, 30},
		{20, 25, 30, 0},
	}
	fmt.Println("shortest tour:", tsp(dist))
	fmt.Printf("states: %d masks × %d cities\n", 1<<len(dist), len(dist))
}

Output

shortest tour: 80
states: 16 masks × 4 cities

The tour of length 80 is 0 → 1 → 3 → 2 → 0 (10 + 25 + 30 + 15).

Choosing the state shape#

Clue in the problem	State
a sequence, answer depends on the last element chosen	`dp[i]` ending at i (LIS, Kadane)
split a string or array into valid pieces	`dp[i]` for the prefix (Word Break, decode ways)
two sequences compared	`dp[i][j]` over prefixes (LCS, edit distance)
best way to process a range, choosing a split or a last element	`dp[i][j]` over intervals, by length
a tree	a tuple returned from each subtree, post-order
which of ≤ 20 items are used	`dp[mask]` or `dp[mask][last]`

Summary#

LIS: O(n²) "ending at i" DP, or O(n log n) with sorted tails and binary search.
Word Break: dp[i] over prefixes; a trie walks all dictionary words from a position at once.
Interval DP fills dp[i][j] by increasing length; think about the last action inside the interval.
Tree DP returns a small tuple per subtree in post-order.
Bitmask DP encodes subsets as integers; it turns n! into 2ⁿ · n² for n up to about 20.

Dynamic programming III

Longest increasing subsequence#

The O(n²) DP

O(n log n) with patience sorting

Word Break: DP plus a trie#

Interval DP#

DP on trees#

Bitmask DP: subsets as integers#

Choosing the state shape#

Summary#

Check your understanding

Practice in Go