DP patterns: state machines, knapsack & strings

package main
 
import "fmt"
 
func main() {
	prices := []int{1, 2, 3, 0, 2}
	// hold: best profit while owning a share; sold: just sold today (must rest tomorrow); rest: free to buy.
	hold, sold, rest := -prices[0], 0, 0
	fmt.Printf("day 0 price=%d hold=%d sold=%d rest=%d\n", prices[0], hold, sold, rest)
	for i, p := range prices[1:] {
		hold, sold, rest = max(hold, rest-p), hold+p, max(rest, sold)
		fmt.Printf("day %d price=%d hold=%d sold=%d rest=%d\n", i+1, p, hold, sold, rest)
	}
	fmt.Println("best:", max(sold, rest))
}

day 0 price=1 hold=-1 sold=0 rest=0
day 1 price=2 hold=-1 sold=1 rest=0
day 2 price=3 hold=-1 sold=2 rest=1
day 3 price=0 hold=1 sold=-1 rest=2
day 4 price=2 hold=1 sold=3 rest=2
best: 3

package main
 
import "fmt"
 
func main() {
	coins, amount := []int{1, 2}, 3
 
	// Coins in the outer loop: each coin is considered once, in a fixed order -> combinations.
	comb := make([]int, amount+1)
	comb[0] = 1
	for _, c := range coins {
		for a := c; a <= amount; a++ {
			comb[a] += comb[a-c]
		}
	}
 
	// Amount in the outer loop: any coin can be last at every step -> ordered sequences.
	perm := make([]int, amount+1)
	perm[0] = 1
	for a := 1; a <= amount; a++ {
		for _, c := range coins {
			if c <= a {
				perm[a] += perm[a-c]
			}
		}
	}
	fmt.Println("combinations:", comb[amount], "(1+1+1, 1+2)")
	fmt.Println("sequences:   ", perm[amount], "(1+1+1, 1+2, 2+1)")
}

combinations: 2 (1+1+1, 1+2)
sequences:    3 (1+1+1, 1+2, 2+1)

package main
 
import (
	"fmt"
	"math"
)
 
// State machines: one variable per state, all updated together each day.
 
// maxProfitUnlimited: any number of transactions.
func maxProfitUnlimited(prices []int) int {
	hold, free := math.MinInt/2, 0
	for _, p := range prices {
		hold, free = max(hold, free-p), max(free, hold+p)
	}
	return free
}
 
// maxProfitCooldown: after selling you must wait one day.
func maxProfitCooldown(prices []int) int {
	hold, sold, rest := math.MinInt/2, 0, 0
	for _, p := range prices {
		hold, sold, rest = max(hold, rest-p), hold+p, max(rest, sold)
	}
	return max(sold, rest)
}
 
// maxProfitFee: pay fee on every sale.
func maxProfitFee(prices []int, fee int) int {
	hold, free := math.MinInt/2, 0
	for _, p := range prices {
		hold, free = max(hold, free-p), max(free, hold+p-fee)
	}
	return free
}
 
// maxProfitK: at most k transactions. hold[j], free[j] = states having started j buys.
func maxProfitK(k int, prices []int) int {
	hold := make([]int, k+1)
	free := make([]int, k+1)
	for j := range hold {
		hold[j] = math.MinInt / 2
	}
	for _, p := range prices {
		for j := k; j >= 1; j-- {
			free[j] = max(free[j], hold[j]+p)
			hold[j] = max(hold[j], free[j-1]-p)
		}
	}
	return free[k]
}
 
// Knapsack family.
 
// coinChange2 counts combinations (order doesn't matter): coins outer.
func coinChange2(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for _, c := range coins {
		for a := c; a <= amount; a++ {
			dp[a] += dp[a-c]
		}
	}
	return dp[amount]
}
 
// combinationSum4 counts ordered sequences: amount outer.
func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1
	for a := 1; a <= target; a++ {
		for _, n := range nums {
			if n <= a {
				dp[a] += dp[a-n]
			}
		}
	}
	return dp[target]
}
 
// findTargetSumWays: choose signs so the total is target. Positives P satisfy P = (sum+target)/2,
// so count subsets with that sum: 0/1 knapsack, iterating sums downward so each number is used once.
func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, n := range nums {
		sum += n
	}
	if target > sum || -target > sum || (sum+target)%2 != 0 {
		return 0
	}
	want := (sum + target) / 2
	dp := make([]int, want+1)
	dp[0] = 1
	for _, n := range nums {
		for s := want; s >= n; s-- {
			dp[s] += dp[s-n]
		}
	}
	return dp[want]
}
 
// String DP.
 
// countPalindromes expands around each of the 2n-1 centers.
func countPalindromes(s string) int {
	count := 0
	for center := 0; center < 2*len(s)-1; center++ {
		l, r := center/2, center/2+center%2
		for l >= 0 && r < len(s) && s[l] == s[r] {
			count++
			l--
			r++
		}
	}
	return count
}
 
// longestPalSubseq: dp[i][j] = longest palindromic subsequence of s[i..j].
func longestPalSubseq(s string) int {
	n := len(s)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i := n - 1; i >= 0; i-- {
		dp[i][i] = 1
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				dp[i][j] = dp[i+1][j-1] + 2
			} else {
				dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			}
		}
	}
	return dp[0][n-1]
}
 
// numDistinct: ways to form t as a subsequence of s. dp[j] = ways to form t[:j]; j goes down.
func numDistinct(s, t string) int {
	dp := make([]int, len(t)+1)
	dp[0] = 1
	for i := 0; i < len(s); i++ {
		for j := len(t); j >= 1; j-- {
			if s[i] == t[j-1] {
				dp[j] += dp[j-1]
			}
		}
	}
	return dp[len(t)]
}
 
// isInterleave: dp[i][j] = s1[:i] and s2[:j] can form s3[:i+j].
func isInterleave(s1, s2, s3 string) bool {
	if len(s1)+len(s2) != len(s3) {
		return false
	}
	dp := make([][]bool, len(s1)+1)
	for i := range dp {
		dp[i] = make([]bool, len(s2)+1)
	}
	dp[0][0] = true
	for i := 0; i <= len(s1); i++ {
		for j := 0; j <= len(s2); j++ {
			if i > 0 && s1[i-1] == s3[i+j-1] && dp[i-1][j] {
				dp[i][j] = true
			}
			if j > 0 && s2[j-1] == s3[i+j-1] && dp[i][j-1] {
				dp[i][j] = true
			}
		}
	}
	return dp[len(s1)][len(s2)]
}
 
func main() {
	fmt.Println(maxProfitUnlimited([]int{7, 1, 5, 3, 6, 4}), maxProfitCooldown([]int{1, 2, 3, 0, 2}), maxProfitFee([]int{1, 3, 2, 8, 4, 9}, 2), maxProfitK(2, []int{3, 2, 6, 5, 0, 3}))
	fmt.Println(coinChange2(5, []int{1, 2, 5}), combinationSum4([]int{1, 2, 3}, 4), findTargetSumWays([]int{1, 1, 1, 1, 1}, 3))
	fmt.Println(countPalindromes("aaa"), longestPalSubseq("bbbab"), numDistinct("rabbbit", "rabbit"))
	fmt.Println(isInterleave("aabcc", "dbbca", "aadbbcbcac"), isInterleave("aabcc", "dbbca", "aadbbbaccc"))
}

7 3 8 7
4 7 5
6 4 3
true false