Memoization (top-down)
Overview
Memoization is 'recursion + a cache'. You write the natural top-down recursive solution, but before recursing, you check if the state is in a cache. After computing, you store the result in the cache.
It is mechanically the most minimal change from a brute-force recursive solution, taking exponential time down to polynomial time by ensuring each state is computed exactly once.
Where used: Dynamic Programming, Expensive recursive functions
Why learn this
- It is usually much easier to write the top-down memoized version of a DP problem because it directly mirrors the mathematical recurrence.
Common mistakes
- Forgetting to check the cache BEFORE recursing: If you do the recursive work and only check/write to the cache at the end, you defeat the entire purpose. The exponential blowup will still happen.
- Forgetting to populate the cache AFTER computing: If you check the cache at the start but forget to save the computed answer before returning, every call will result in a cache miss.
- Using a mutable default argument as the cache in Python: Defining `def solve(n, cache={})` in Python means the cache persists across entirely different top-level calls of `solve`, leading to incorrect results on subsequent test cases.
Recall questions
- What is the time complexity of a memoized DP solution?
- What is the space complexity of a memoized DP solution?
Understanding checks
Find the bug in this memoized function: ```python def fib(n, memo=None): if memo is None: memo = {} if n <= 1: return n ans = fib(n-1, memo) + fib(n-2, memo) return ans ```
It fails to check the cache at the start, and it fails to write to the cache at the end.
Without `if n in memo: return memo[n]` and `memo[n] = ans`, this is just regular exponential recursion that creates an unused dictionary.
In Python, why is `def dfs(state, memo={})` dangerous for LeetCode problems?
The dictionary is created once when the function is defined. It will retain cached values from Test Case 1 when Test Case 2 runs, causing wrong answers.
Default arguments are evaluated at function definition time in Python. Always use `memo=None` and initialize it inside the function.
Practice tasks
Add memoization
Modify this recursive function to use a `memo` dictionary. Make sure to pass it down correctly and not use a mutable default argument.
Challenge
Identify cache hits
In computing `fib(5)` with memoization, the cache prevents redundant work. Which function call is the first one to trigger a cache hit (i.e. returns immediately from the cache)?
Continue learning
Previous: State & transition
Next: Tabulation (bottom-up)