Why it matters
Recognizing when a problem is DP-suitable is a key skill. Many interview questions and real problems turn out to be DP variants. Once you see the pattern, solutions become mechanical.
The architecture
Two conditions: optimal substructure (solution built from optimal subproblem solutions) and overlapping subproblems (same subproblem appears many times).
Fibonacci as canonical example: naive recursion is O(2^n); memoized is O(n).
How it works end to end
Top-down: write natural recursion, then add a memo table. Each subproblem computed once.
Bottom-up: identify subproblem ordering; fill table iteratively from base cases. Often more space-efficient.
State design: choose state variables carefully. Wrong state design makes the problem exponential.
Space optimization: many DP problems only need the last few rows of the table. Reduce O(n²) space to O(n).