# Dynamic programming

> Solve problems with overlapping subproblems by computing each subproblem once and reusing the answer: define the state, the transition and the order.

Concept · Algorithms & complexity · https://levelcode.org/concepts/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:

```go
// 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](https://levelcode.org/roadmaps/software-engineer/algorithms).