2-D Dynamic Programming

// UniquePaths: robot moves right or down on an m×n grid.
// dp[c] holds the ways to reach column c of the current row; it is updated row by row in one slice.
func UniquePaths(m, n int) int {
	dp := make([]int, n)
	for c := range dp {
		dp[c] = 1 // top row: only one way to reach each cell
	}
	for r := 1; r < m; r++ {
		for c := 1; c < n; c++ {
			dp[c] += dp[c-1] // from above (old dp[c]) + from the left (new dp[c-1])
		}
	}
	return dp[n-1]
}

// LongestCommonSubsequence.
// State: dp[i][j] = LCS length of a[:i] and b[:j]. Row 0 and column 0 are the empty-prefix base cases.
func LongestCommonSubsequence(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 // match: extend the diagonal
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // drop one character
			}
		}
	}
	return dp[len(a)][len(b)]
}

// MinDistance: fewest insert / delete / replace edits to turn a into b.
// State: dp[i][j] = edits to turn a[:i] into b[:j].
func MinDistance(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 := 0; j <= len(b); j++ {
		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]) // replace, delete, insert
			}
		}
	}
	return dp[len(a)][len(b)]
}

// Change: number of COMBINATIONS of coins that make amount.
// Coins are the OUTER loop, so each combination is counted once, in a fixed coin order.
func Change(amount int, coins []int) int {
	ways := make([]int, amount+1)
	ways[0] = 1
	for _, coin := range coins {
		for a := coin; a <= amount; a++ {
			ways[a] += ways[a-coin]
		}
	}
	return ways[amount]
}

// FindTargetSumWays: choose + or - for every number so the total is target.
// The + group P and - group N satisfy P - N = target and P + N = sum, so P = (sum + target) / 2:
// count subsets that add up to P.
func FindTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, n := range nums {
		sum += n
	}
	if (sum+target)%2 != 0 || sum+target < 0 || target > sum || -target > sum {
		return 0
	}
	want := (sum + target) / 2
	ways := make([]int, want+1)
	ways[0] = 1
	for _, n := range nums {
		for s := want; s >= n; s-- { // descending: each number used at most once
			ways[s] += ways[s-n]
		}
	}
	return ways[want]
}

// MaxProfitCooldown: unlimited trades, but you must rest one day after selling.
// Three states per day: holding a stock, just sold (cooling down), or resting with nothing.
func MaxProfitCooldown(prices []int) int {
	hold, sold, rest := -1<<31, 0, 0
	for _, p := range prices {
		prevSold := sold
		sold = hold + p
		hold = max(hold, rest-p)
		rest = max(rest, prevSold)
	}
	return max(sold, rest)
}

// IsInterleave: can s3 be formed by weaving s1 and s2 without reordering either?
// dp[i][j] = the first i letters of s1 and j letters of s2 can form the first i+j letters of s3.
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 && dp[i-1][j] && s1[i-1] == s3[i+j-1] {
				dp[i][j] = true
			}
			if j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1] {
				dp[i][j] = true
			}
		}
	}
	return dp[len(s1)][len(s2)]
}

// LongestIncreasingPath: memoized DFS. Strictly increasing steps cannot form a cycle,
// so every cell's answer can be cached the first time it is computed.
func LongestIncreasingPath(m [][]int) int {
	if len(m) == 0 {
		return 0
	}
	memo := make([][]int, len(m))
	for i := range memo {
		memo[i] = make([]int, len(m[0]))
	}
	var dfs func(r, c int) int
	dfs = func(r, c int) int {
		if memo[r][c] != 0 {
			return memo[r][c]
		}
		best := 1
		for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
			nr, nc := r+d[0], c+d[1]
			if nr >= 0 && nr < len(m) && nc >= 0 && nc < len(m[0]) && m[nr][nc] > m[r][c] {
				best = max(best, 1+dfs(nr, nc))
			}
		}
		memo[r][c] = best
		return best
	}
	longest := 0
	for r := range m {
		for c := range m[r] {
			longest = max(longest, dfs(r, c))
		}
	}
	return longest
}

// NumDistinct: how many ways does t appear as a subsequence of s?
// dp[j] = ways to build the first j letters of t from the part of s seen so far.
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-- { // descending so dp[j-1] still holds the previous row
			if s[i] == t[j-1] {
				dp[j] += dp[j-1]
			}
		}
	}
	return dp[len(t)]
}

// MaxCoins: interval DP. Choose the balloon k that bursts LAST in (l, r);
// then its neighbours are the fixed ends l and r, and the two sides are independent subproblems.
func MaxCoins(nums []int) int {
	a := append([]int{1}, append(append([]int{}, nums...), 1)...)
	n := len(a)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for length := 2; length < n; length++ {
		for l := 0; l+length < n; l++ {
			r := l + length
			for k := l + 1; k < r; k++ {
				dp[l][r] = max(dp[l][r], dp[l][k]+dp[k][r]+a[l]*a[k]*a[r])
			}
		}
	}
	return dp[0][n-1]
}

// IsMatch: regular expression matching with '.' and '*'.
// dp[i][j] = the first i characters of s match the first j characters of p.
func IsMatch(s, p string) bool {
	dp := make([][]bool, len(s)+1)
	for i := range dp {
		dp[i] = make([]bool, len(p)+1)
	}
	dp[0][0] = true
	for j := 2; j <= len(p); j++ {
		if p[j-1] == '*' {
			dp[0][j] = dp[0][j-2] // "a*" can match the empty string
		}
	}
	for i := 1; i <= len(s); i++ {
		for j := 1; j <= len(p); j++ {
			if p[j-1] == '*' {
				dp[i][j] = dp[i][j-2] // zero copies of the starred letter
				if p[j-2] == '.' || p[j-2] == s[i-1] {
					dp[i][j] = dp[i][j] || dp[i-1][j] // one more copy
				}
			} else if p[j-1] == '.' || p[j-1] == s[i-1] {
				dp[i][j] = dp[i-1][j-1]
			}
		}
	}
	return dp[len(s)][len(p)]
}