DSA · Lesson 14 of 20 · 4 min
Dynamic Programming I: Memoization
This is how you turn an exponential-time recursive solution into a linear one, and explain the trade-off in an interview.
Dynamic Programming (DP) is an optimization technique. Memoization is the top-down, recursive way to do it. You use it when you find a recursive solution that's correct but too slow because it solves the same subproblem over and over.
You trade space for time. By storing the results of subproblems in a cache, you avoid re-computing them, drastically speeding up your code.
The Pattern: Overlapping Subproblems
The signal for memoization is a recursive function that repeatedly calls itself with the same arguments. Consider the Fibonacci sequence: fib(n) = fib(n-1) + fib(n-2).
To calculate fib(5), you need fib(4) and fib(3).
To calculate fib(4), you need fib(3) and fib(2).
You can see fib(3) is needed twice. As n grows, the number of these "overlapping subproblems" explodes, leading to an exponential number of calls. This is the problem memoization solves.
Step 1: Write the Brute-Force Solution
In an interview, always start with the simple, brute-force recursive solution. It shows you understand the problem's structure before you optimize it. It also serves as the scaffold for your memoized solution.
Here is the naive, exponential-time Fibonacci function.
function fib(n: number): number {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
This works, but its time complexity is O(2^n). For n=40, this is over a billion operations. Unacceptable. This is your moment to identify the inefficiency and propose the fix.
Step 2: Add a Cache to Memoize Results
The fix is to add a cache (a plain object or a Map) to store results as they are computed. The logic is always the same three steps, inserted at the top of your recursive function.
- Check if the result for the current arguments exists in the cache. If yes, return it immediately.
- If not, compute the result as before.
- Before returning the result, store it in the cache.
function fibMemo(n: number, memo: { [key: number]: number } = {}): number {
// 1. Check the cache
if (n in memo) {
return memo[n];
}
if (n <= 1) {
return n;
}
// 2. Compute if not in cache
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
// 3. Store the result before returning
memo[n] = result;
return result;
}
By adding the memo object, we ensure that fibMemo for any given n is only ever computed once. The time complexity drops to O(n).
The trap: Forgetting to pass the memo object in the recursive calls. If you call fibMemo(n - 1) instead of fibMemo(n - 1, memo), each sub-problem gets a new, empty cache, and your optimization does nothing.
The space complexity is now O(n) to hold the cache and O(n) for the recursion call stack, for a total of O(n). This is the trade-off you must articulate.
Handling Functions with Multiple Arguments
When your function takes multiple arguments, you need a strategy for creating a unique cache key. A common method is to create a string by joining the arguments with a delimiter.
Consider the Grid Traveler problem: how many ways can you travel from the top-left to the bottom-right of an m x n grid, moving only right or down?
The state is defined by two numbers, m and n. A simple key is m + ',' + n.
function gridTraveler(m: number, n: number, memo: { [key: string]: number } = {}): number {
const key = `${m},${n}`;
if (key in memo) {
return memo[key];
}
if (m === 1 && n === 1) return 1;
if (m === 0 || n === 0) return 0;
const result = gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo);
memo[key] = result;
return result;
}
A subtle improvement: In this specific problem,
gridTraveler(m, n)is the same asgridTraveler(n, m). You can optimize the cache by creating a canonical key, likeMath.min(m, n) + ',' + Math.max(m, n). This demonstrates attention to detail.
The Memoization Playbook for Interviews
When you spot a problem with overlapping subproblems, follow these steps to present a clean, well-reasoned solution.
- State the brute-force approach. Acknowledge the recursive nature of the problem.
- Code the brute-force solution. Get a working, albeit slow, solution on the board.
- Analyze its complexity. Point out the exponential time complexity and explain that it's due to re-computing the same subproblems. Use a small example like
fib(4)to illustrate the repeated work. - Introduce memoization. Describe the "cache-and-return" strategy and the time-space trade-off.
- Modify the code. Add the memo object, the cache check, and the cache store.
- Analyze the improved complexity. Explain that the time is now proportional to the number of unique subproblems (
O(n)for Fibonacci,O(m*n)for Grid Traveler) and the space is also proportional to that number.
This flow shows a methodical problem-solving process, which is exactly what interviewers are looking for.
Try it
Take the classic Climbing Stairs problem: you can climb 1 or 2 steps at a time. How many distinct ways can you climb to the top of n stairs? First, write the brute-force recursive solution. Then, add memoization to make it efficient. The state you need to cache is simply n.
Next: We'll move on to a data structure for efficiently managing ordered elements: Heaps and Priority Queues.
Lock it in — apply this lesson under interview conditions.