Advanced · Module 15 · Lesson 1 of 6
Memoization
When a recursion solves the same subproblem many times, store each answer the first time and look it up after that. The cost becomes the number of distinct subproblems times the work for each.
By the end you can
- Recognize overlapping subproblems and optimal substructure in a recursive solution
- Add memoization to a recursive function, keyed by exactly the arguments that define a subproblem
- Estimate a memoized solution's cost as states × work per state
Builds on Base cases and recursion trees.
01 · A question first
You climb a staircase taking one or two steps at a time. How many different ways are there to climb 40 steps? The plain recursion makes more than 330 million calls to answer. Adding one dictionary brings it down to 79. Which calls does the dictionary skip?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Recursion that repeats itself
- Two properties
- Memoization
- Counting the cost
- Memoizing a search
- A checklist for memoizing
- Where memoization falls short
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem