Dynamic programming

Dynamic programming (DP) solves a problem by breaking it into smaller subproblems, solving each once, and storing the answers for reuse. It applies when a problem has two properties:

• Overlapping subproblems: a naive recursive solution solves the same subproblem many times.
• Optimal substructure: the best answer can be built from best answers to smaller subproblems.

Fibonacci is the textbook case: fib(n) = fib(n-1) + fib(n-2) recomputed naively takes exponential time, because fib(n-2) is computed inside both branches. Storing each result makes it linear.

#The recipe

Every DP solution answers four questions:

1. State: what does dp[i] (or dp[i][j]) mean, in one sentence?
2. Transition: how is a state computed from smaller states?
3. Base cases: the smallest states, known directly.
4. Order: fill states so each one's dependencies are ready — or recurse with a cache.

Example — the fewest coins that make an amount:

// MinCoins returns the fewest coins summing to amount, or -1.
func MinCoins(coins []int, amount int) int {
	dp := make([]int, amount+1) // dp[a] = fewest coins for amount a
	for a := 1; a <= amount; a++ {
		dp[a] = math.MaxInt
		for _, c := range coins {
			if c <= a && dp[a-c] != math.MaxInt {
				dp[a] = min(dp[a], dp[a-c]+1)
			}
		}
	}
	if dp[amount] == math.MaxInt {
		return -1
	}
	return dp[amount]
}

State: fewest coins for amount a. Transition: try each coin as the last one. Base case: dp[0] = 0. Order: increasing amounts. O(amount × coins) time.

#Top-down or bottom-up

Memoization (top-down) keeps the natural recursion and caches results in a map; it only computes states that are actually needed. Tabulation (bottom-up) fills an array in order; it avoids recursion depth limits and often lets you keep only the last row or two, reducing memory.

#DP versus greedy

A greedy algorithm takes the locally best choice and never reconsiders. It's simpler when it's correct, but for coins {1, 3, 4} and amount 6, greedy picks 4+1+1 while DP finds 3+3. If you can't prove the greedy choice is always safe, use DP. More examples are in the algorithms lesson.