Dynamic Programming

// climbBrute is the plain recursion: correct but O(2^n) because the same
// subproblems are solved again and again.
func climbBrute(n int) int {
	if n <= 1 {
		return 1
	}
	return climbBrute(n-1) + climbBrute(n-2)
}

// Template: top-down. Define the state, write the transition, handle base cases,
// and cache every answer so each state is computed once.
// Here the state is just `i` (a 1-D problem); more parameters -> a map or a 2-D table.
func memoTemplate(n int) int {
	memo := make([]int, n+1)
	for i := range memo {
		memo[i] = -1 // -1 = "not computed yet"
	}
	var solve func(i int) int
	solve = func(i int) int {
		if i <= 1 { // base case: the smallest subproblems
			return 1
		}
		if memo[i] != -1 { // already solved: reuse
			return memo[i]
		}
		memo[i] = solve(i-1) + solve(i-2) // transition: combine smaller states
		return memo[i]
	}
	return solve(n)
}

// ClimbStairs: ways to reach step n taking 1 or 2 steps at a time.
// Bottom-up with O(1) space: dp[i] only needs dp[i-1] and dp[i-2].
func ClimbStairs(n int) int {
	prev, cur := 1, 1 // ways to reach step 0 and step 1
	for i := 2; i <= n; i++ {
		prev, cur = cur, prev+cur
	}
	return cur
}

// Rob: max loot from a row of houses, never two adjacent.
// State: best loot using houses[0..i]. Transition: skip house i, or take it + best up to i-2.
func Rob(nums []int) int {
	take, skip := 0, 0 // best if we may use the previous house / best up to two houses ago
	for _, v := range nums {
		take, skip = max(skip+v, take), take
	}
	return take
}

// CoinChange: fewest coins that make up amount, or -1.
// State: dp[a] = fewest coins for amount a. Order: small amounts first.
func CoinChange(coins []int, amount int) int {
	inf := amount + 1 // larger than any real answer
	dp := make([]int, amount+1)
	for a := 1; a <= amount; a++ {
		dp[a] = inf
		for _, c := range coins {
			if c <= a {
				dp[a] = min(dp[a], dp[a-c]+1)
			}
		}
	}
	if dp[amount] >= inf {
		return -1
	}
	return dp[amount]
}

// 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)]
}

// Knapsack: max value using each item at most once within capacity (0/1 knapsack).
// 1-D table; loop capacity DOWNWARD so an item cannot be counted twice.
func Knapsack(weights, values []int, capacity int) int {
	dp := make([]int, capacity+1)
	for i, w := range weights {
		for c := capacity; c >= w; c-- {
			dp[c] = max(dp[c], dp[c-w]+values[i])
		}
	}
	return dp[capacity]
}

// LengthOfLIS: length of the longest strictly increasing subsequence.
// State: dp[i] = best length ending exactly at nums[i].
func LengthOfLIS(nums []int) int {
	best := 0
	dp := make([]int, len(nums))
	for i := range nums {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		best = max(best, dp[i])
	}
	return best
}

// MinCostClimbingStairs: you may start on step 0 or 1; the top is just past the last step.
// State: cost to stand on step i = cost[i] + the cheaper of the two steps you could have come from.
func MinCostClimbingStairs(cost []int) int {
	a, b := 0, 0 // cheapest cost to reach the two most recent steps (starting is free)
	for i := 2; i <= len(cost); i++ {
		a, b = b, min(b+cost[i-1], a+cost[i-2])
	}
	return b
}

// RobCircle: houses form a circle, so the first and last cannot both be robbed.
// Solve the line twice (without the last house, then without the first) and take the better one.
func RobCircle(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	return max(Rob(nums[:len(nums)-1]), Rob(nums[1:]))
}

// NumDecodings: "12" can be "AB" (1,2) or "L" (12).
// dp[i] = ways to decode the first i digits = (last digit alone is 1-9) + (last two digits are 10-26).
func NumDecodings(s string) int {
	if len(s) == 0 || s[0] == '0' {
		return 0
	}
	prev2, prev1 := 1, 1 // ways for 0 digits and for 1 digit
	for i := 2; i <= len(s); i++ {
		cur := 0
		if s[i-1] != '0' {
			cur += prev1
		}
		if two := int(s[i-2]-'0')*10 + int(s[i-1]-'0'); two >= 10 && two <= 26 {
			cur += prev2
		}
		prev2, prev1 = prev1, cur
	}
	return prev1
}

// WordBreak: can s be split into dictionary words?
// dp[i] = the first i letters can be split, true when some earlier cut j works AND s[j:i] is a word.
func WordBreak(s string, words []string) bool {
	dict := make(map[string]bool, len(words))
	for _, w := range words {
		dict[w] = true
	}
	dp := make([]bool, len(s)+1)
	dp[0] = true
	for i := 1; i <= len(s); i++ {
		for j := 0; j < i; j++ {
			if dp[j] && dict[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)]
}

// CanPartition: split into two subsets with equal sums = can some numbers reach exactly half?
// reachable[s] means "some chosen numbers add up to s". Loop DOWNWARDS so each number is used once.
func CanPartition(nums []int) bool {
	total := 0
	for _, n := range nums {
		total += n
	}
	if total%2 != 0 {
		return false
	}
	half := total / 2
	reachable := make([]bool, half+1)
	reachable[0] = true
	for _, n := range nums {
		for s := half; s >= n; s-- {
			reachable[s] = reachable[s] || reachable[s-n]
		}
	}
	return reachable[half]
}

// MaxProduct: a negative number can flip the smallest product into the largest,
// so track BOTH the max and the min product of a subarray ending here.
func MaxProduct(nums []int) int {
	best, hi, lo := nums[0], nums[0], nums[0]
	for _, n := range nums[1:] {
		a, b := hi*n, lo*n
		hi = max(n, max(a, b))
		lo = min(n, min(a, b))
		best = max(best, hi)
	}
	return best
}

// LongestPalindrome: every palindrome has a centre, and there are 2n-1 centres
// (n letters and n-1 gaps between letters). Expand outward from each while the ends match.
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 s {
		expand(i, i)   // odd length, centred on a letter
		expand(i, i+1) // even length, centred between two letters
	}
	return s[start : start+length]
}

// CountSubstrings: the same expansion, counting every success instead of keeping the longest.
func CountSubstrings(s string) int {
	count := 0
	expand := func(l, r int) {
		for l >= 0 && r < len(s) && s[l] == s[r] {
			count++
			l--
			r++
		}
	}
	for i := range s {
		expand(i, i)
		expand(i, i+1)
	}
	return count
}