Dynamic Programming
Dynamic programming evaluates a directed acyclic graph of subproblems once and reuses their results. Memoization and tabulation are execution strategies; the hard part is defining a sufficient state and a correct recurrence.
Design checklist
- State: What minimum information makes the remaining problem independent of the path used to reach it?
- Value: What does
dp[state]mean—feasibility, count, minimum cost, maximum value, or a witness? - Transition: Which smaller states can produce this state?
- Base cases: What are the smallest valid subproblems?
- Order: Does every dependency exist before it is read?
- Answer: Which state or aggregate contains the requested output?
Top-down versus bottom-up
| Approach | Strength | Cost |
|---|---|---|
| Memoized recursion | evaluates only reached states; mirrors recurrence | call-stack depth and cache-key design |
| Bottom-up table | explicit order; easier space compression | may evaluate irrelevant states |
State count multiplied by transition work gives the first complexity estimate. Memory can be compressed only when overwritten states will never be needed for future transitions or reconstruction.
Correctness pattern
Prove that the state captures all relevant history, then use induction over the dependency order: assuming smaller states are correct, the recurrence considers every valid final choice and selects or combines them according to the objective.
When DP is the wrong tool
DP is unhelpful when the chosen state still depends on unbounded history, the state space is larger than direct search, or a greedy/exchange property removes the need to compare alternatives. Expanding state can restore correctness, but may make the algorithm impractical.