Chapter 50
HomeDynamic programming (DP) is recursion + memoisation — but with a systematic approach. You break a problem into overlapping subproblems, solve each once, and build up to the full answer. If greedy is "act now, never look back," DP is "explore everything, but don't explore anything twice."
1. Optimal substructure
An optimal solution to the whole problem contains optimal solutions to its subproblems. Same requirement as greedy — but DP doesn't need the greedy choice property.
2. Overlapping subproblems
The same subproblems are solved multiple times. Memoisation (or bottom-up tabulation) lets you solve each once. If subproblems don't overlap, you have divide-and-conquer instead (merge sort, quick sort).
Top-down (memoisation)
Start with the full problem, recurse down, cache results. Easier to write because it mirrors the recursive formulation. Risk: stack overflow for deep recursion.
Bottom-up (tabulation)
Start with the smallest subproblems, fill a table iteratively, build up to the full problem. No recursion overhead. Often allows space optimisation (only keep the last row).
// Both approaches compute the same thing — the order differs. // // Top-down: fib(5) → fib(4) + fib(3) → fib(3) + fib(2) ... // Bottom-up: fib(0), fib(1), fib(2), ..., fib(5) // // Top-down is often called "memoisation" (memo-isation). // Bottom-up is often called "tabulation" (table-filling). // Know both — use whichever is easier for the problem.
When solving any DP problem, answer these four questions:
1. What is the state?
What parameters uniquely describe a subproblem? (e.g. i for position, w for weight remaining)
2. What is the recurrence?
How does a state relate to smaller states? (e.g. dp[i] = dp[i-1] + dp[i-2])
3. What are the base cases?
What states can be answered immediately without DP? (e.g. dp[0] = 0, dp[1] = 1)
4. What is the answer?
Where in the table is the final answer? (e.g. dp[N], dp[N][W], max(dp[N]))