Course contentsShow
← Computer Science
Lesson 916 of 2,87222. Dynamic ProgrammingFree lesson

Memoization (Top-Down DP)

Store results of expensive function calls and return cached results when the same inputs occur again.

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

  1. Start with your recursive solution (assumes you've identified overlapping subproblems)
  2. Add a cache/memo (usually a dictionary or array)
  3. Before computing: Check if the answer is already in the cache
  4. 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.