Memoization Pattern
What is Memoization?
Memoization is a top-down dynamic programming technique where we solve the problem recursively and store the results of subproblems to avoid redundant calculations.
It's essentially an optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again.
When to Use Memoization
Memoization is useful when:
- The problem has a natural recursive structure
- The recursive solution has overlapping subproblems
- You prefer a top-down approach that follows the natural recursive structure
- You only need to compute a subset of all possible states
Memoization Template
- Write a recursive function that solves the problem
- Add a memo object/array as a parameter to store results
- Before computing anything, check if the result for the current state is already in the memo
- After computing the result, store it in the memo before returning
Example: Fibonacci
Here's a memoized solution for computing the nth Fibonacci number:
Example: Longest Common Subsequence
Here's a memoized solution for finding the longest common subsequence of two strings:
Example: Coin Change
Here's a memoized solution for the coin change problem:
Pros and Cons of Memoization
Pros:
- Easy to implement from a recursive solution
- Computes only the needed states
- Follows the natural recursive structure of the problem
Cons:
- May cause stack overflow for large inputs due to recursion
- Slightly more overhead due to recursive function calls
- May be less intuitive for problems that are naturally iterative
Pattern 1: Memoization
Learn how to optimize recursive solutions by storing and reusing results of subproblems.
What is Memoization?
Memoization is a top-down dynamic programming technique where we solve the problem recursively and store the results of subproblems to avoid redundant calculations.
It's essentially an optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again.
Key Insight: Memoization transforms an exponential time recursive algorithm into a polynomial time algorithm by eliminating redundant calculations of overlapping subproblems.
When to Use Memoization
Natural Recursion
When the problem has a natural recursive structure and the recursive solution is intuitive but inefficient due to overlapping subproblems.
Partial Computation
When you only need to compute a subset of all possible states, as memoization computes states on-demand rather than computing all possible states.
Complex State Transitions
When the state transitions are complex and it's easier to express them recursively than iteratively.
The Memoization Template
1Recursive Function
Start with a recursive function that solves the problem. Identify the parameters that define the state of a subproblem.
2Add Memo
Add a memo object or array as a parameter to store results. Create a unique key for each state.
3Check Memo
Before computing anything, check if the result for the current state is already in the memo. If so, return it.
4Store Result
After computing the result, store it in the memo before returning. This ensures the result is available for future calls with the same state.
Pseudocode Template:
function solve(params, memo = {}):
// Create a key for the current state
key = createKey(params)
// Check if we've already computed this state
if key in memo:
return memo[key]
// Base cases
if isBaseCase(params):
return baseValue
// Recursive case with memoization
result = compute using recursive calls to solve()
// Store the result in memo before returning
memo[key] = result
return resultExample: Fibonacci
Here's a memoized solution for computing the nth Fibonacci number:
123456789101112131415function fibonacci(n, memo = {}) { // Check if we've already computed this value if (n in memo) return memo[n]; // Base cases if (n <= 1) return n; // Recursive case with memoization memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); return memo[n];} // Example usage:console.log(fibonacci(10)); // Output: 55console.log(fibonacci(40)); // Output: 102334155 (would be very slow without memoization)How it works: Without memoization, computing fibonacci(n) would take O(2^n) time due to redundant calculations. With memoization, we store the result of each fibonacci(k) call, so we compute each Fibonacci number only once, reducing the time complexity to O(n).
Example: Longest Common Subsequence
Here's a memoized solution for finding the longest common subsequence of two strings:
12345678910111213141516171819202122232425262728function longestCommonSubsequence(text1, text2, i = 0, j = 0, memo = {}) { // Create a key for the current state const key = i + ',' + j; // Check if we've already computed this state if (key in memo) return memo[key]; // Base case: if we've reached the end of either string if (i === text1.length || j === text2.length) return 0; // If the current characters match if (text1[i] === text2[j]) { memo[key] = 1 + longestCommonSubsequence(text1, text2, i + 1, j + 1, memo); } else { // If they don't match, take the maximum of two possibilities memo[key] = Math.max( longestCommonSubsequence(text1, text2, i + 1, j, memo), longestCommonSubsequence(text1, text2, i, j + 1, memo) ); } return memo[key];} // Example usage:console.log(longestCommonSubsequence("abcde", "ace")); // Output: 3 (LCS is "ace")console.log(longestCommonSubsequence("abc", "abc")); // Output: 3 (LCS is "abc")console.log(longestCommonSubsequence("abc", "def")); // Output: 0 (no common subsequence)How it works: We use two indices i and j to represent our current position in both strings. At each step, if the characters match, we include them in the LCS and move both indices. If they don't match, we try both possibilities (skip a character in either string) and take the maximum. Memoization reduces the time complexity from O(2^(m+n)) to O(m*n).
Example: Coin Change
Here's a memoized solution for the coin change problem:
123456789101112131415161718192021222324252627282930function coinChange(coins, amount, index = 0, memo = {}) { // Create a key for the current state const key = amount + ',' + index; // Check if we've already computed this state if (key in memo) return memo[key]; // Base cases if (amount === 0) return 0; if (amount < 0 || index === coins.length) return Infinity; // Two options: include the current coin or skip it const includeCoin = 1 + coinChange(coins, amount - coins[index], index, memo); const skipCoin = coinChange(coins, amount, index + 1, memo); // Store the minimum in memo and return memo[key] = Math.min(includeCoin, skipCoin); return memo[key];} // Wrapper function to handle the resultfunction minCoins(coins, amount) { const result = coinChange(coins, amount); return result === Infinity ? -1 : result;} // Example usage:console.log(minCoins([1, 2, 5], 11)); // Output: 3 (5 + 5 + 1)console.log(minCoins([2], 3)); // Output: -1 (not possible)console.log(minCoins([1, 2, 5], 0)); // Output: 0 (no coins needed)How it works: For each coin, we have two choices: include it in our solution or skip it. We recursively try both options and take the minimum number of coins needed. Memoization ensures we don't recompute the same subproblems, reducing the time complexity from exponential to O(amount * coins.length).
Pros and Cons of Memoization
Pros
- Easy to implement from a recursive solution
- Computes only the needed states, which can be more efficient if you don't need all states
- Follows the natural recursive structure of the problem, making it more intuitive for some problems
- Can handle complex state spaces where it's difficult to determine the order of computation
- Can be more concise and easier to understand for some problems
Cons
- May cause stack overflow for large inputs due to recursion
- Slightly more overhead due to recursive function calls
- May be less intuitive for problems that are naturally iterative
- Can be harder to optimize for space complexity
- Might not be as efficient as tabulation for problems where all states need to be computed