Dynamic Programming
The problem
Some recursive problems recompute the same subproblem exponentially many times (naive Fibonacci being the classic case), wasting enormous work — dynamic programming eliminates that waste by remembering (caching) subproblem answers instead of recomputing them.
Why now
Recurrence relations already showed that a naive recursive solution's cost is governed by its recurrence, and that recurrence can be exponential. Dynamic programming is the direct fix: store each subproblem's answer once, in a table or cache, turning an exponential recurrence into a polynomial one by trading memory for time.
Mental model
If you've solved a subproblem before, don't solve it again — write the answer down and look it up next time. That's the entire idea; 'dynamic programming' is just disciplined memoization, either top-down (recursion plus a cache) or bottom-up (filling a table from the smallest subproblems up).
Requires
- Recurrence RelationsMathematical Thinking
Dynamic programming targets exactly the problems recurrence relations describe — its entire value proposition is turning an expensive recurrence's repeated subproblems into a cheap lookup, which requires already seeing the problem as a recurrence.
- RecursionProgramming Fundamentals
Top-down dynamic programming is recursion plus a cache; you need a correct recursive solution before memoizing it makes sense.
Helps
- Hash TablesComputer Science Fundamentals
A memoization cache is typically a hash table mapping subproblem inputs to their computed answers — useful to already know how to build one, though a plain array works for simple cases.
Used in
- Memoized Fibonacci and other classic recursive-with-overlap problems
- Shortest-edit-distance algorithms (diff tools, spell checkers)
- Resource-allocation and knapsack-style optimization problems
- Compiler and database query optimizers (choosing an optimal execution plan)
Projects
- Implement naive recursive Fibonacci, time it at n=35, then add memoization and compare the runtime difference directly
- Solve the edit-distance problem (minimum operations to transform one string into another) using bottom-up dynamic programming
Examples
- Naive fib(40) makes over a billion redundant calls; memoized fib(40) makes 40
- A spell checker's 'did you mean' suggestion is powered by edit-distance dynamic programming
Resources
Mastery checklist
- I can identify when a recursive solution has overlapping subproblems that justify memoization
- I can convert a naive exponential recursive solution into a memoized polynomial one
- I can write a bottom-up (tabulation) solution as an alternative to top-down memoization
- I can explain the space/time tradeoff dynamic programming makes