BUILD YOUR INTUITION
Dynamic Programming Define a reusable answer for each state, then compute states from already solved smaller ones.
When should this come to mind? Define a reusable answer for each state, then compute states from already solved smaller ones.
What makes it work State meaning and dependency order must be explicit. Unreachable states need a separate representation.
When to choose something else If a valid greedy choice can be proven and no overlapping states remain, DP may add unnecessary work.
COMPLEXITY GUIDE TIME States × work per state
SPACE Number of retained states
Common mistakes Wrong base case Using an unreachable state as zero Optimizing space before understanding dependencies At the whiteboard Move from recursion to memoization, then bottom-up order, and only then optimize retained state.
Recursion Memoization Bottom-up DP Space optimization First name the repeated state. Cache its answer, order its dependencies, then retain only states still needed. Coin Change demonstrates the bottom-up step.
See the pattern in action Change the input. Follow the state. Make it yours.