Dynamic Programming
Choose a state representation, then build larger answers from solved states.
The idea
Dynamic programming becomes easier when you first name the state representation. 1D states use one progress index, Grid states use two coordinates, Knapsack states track a reusable budget, and Digit States build bounded numbers position by position.
This visualization makes the state transitions behind dynamic programming explicit, one decision at a time.
When to reach for it
- The problem exhibits this pattern's defining invariant.
- A direct brute-force approach repeats work or explores unnecessary choices.
- You need a standard interview-ready template.
Language-independent template
define the state representation and base cases
iterate in dependency order
transition from already-solved statesComplexity — time Depends on the state space, space Depends on stored states.
Common mistakes
- Choosing the wrong state or invariant.
- Updating state before preserving the value needed next.
- Missing a boundary or base case.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Count distinct ways to reach the top using one- or two-step moves.
Find the minimum insertions, deletions, and replacements to transform one string.
Choose a bursting order that maximizes collected coins.