Memoization (Top-Down DP)
What you'll learn: How to dramatically speed up recursive algorithms by caching results you've already computed.
The Core Idea
Imagine you're solving a problem recursively, like calculating Fibonacci numbers. The naive recursive approach recalculates the same values over and over—fib(5) might compute fib(3) dozens of times!
Memoization is simple: store the result of each function call in a lookup table (like a hash map), and before doing expensive work, check if you've already solved that exact subproblem. If you have, return the cached answer instantly instead of recalculating.
How It Works
- Start with your recursive solution (assumes you've identified overlapping subproblems)
- Add a cache/memo (usually a dictionary or array)
- Before computing: Check if the answer is already in the cache
- After computing: Store the result in the cache before returning
This is called "top-down" Dynamic Programming because you start with the original problem and break it down into smaller subproblems naturally through recursion, caching as you go.
Plain-English Analogy
Think of a student asking you math problems. Without memoization, every time they ask "What's 7 × 8?", you recalculate it. With memoization, after answering once, you write it in a notebook. Next time they ask, you just look it up—instant answer!
Why It Matters
Memoization transforms exponential-time algorithms into polynomial-time ones by ensuring each unique subproblem is solved exactly once. It's the easiest way to optimize recursive solutions with overlapping subproblems—you keep your clean recursive structure while gaining efficiency.
Key Takeaway: Memoization speeds up recursion by caching previously computed results, ensuring each subproblem is solved only once—turning your recursive solution into an efficient dynamic programming algorithm.