Loading learning content...
Understanding that memoization works is one thing. Implementing it correctly and efficiently is another. The memo cache is the heart of any memoized solution, and its design directly impacts performance, memory usage, and code clarity.
In this page, we move from concept to craft. We'll explore two fundamental approaches to memo storage—dictionaries (hash maps) and arrays—and understand when each excels. We'll master key design for multi-parameter problems, handle edge cases that trip up beginners, and learn language-specific idioms that make memoization elegant.
By the end, you'll be able to implement memo caches for any problem with confidence, choosing the right data structure and designing keys that are both correct and efficient.
You'll master the practical mechanics of memo implementation: when to use dictionaries vs arrays, how to design composite keys for multi-dimensional state, initialization patterns, sentinel values, and clean API design. These skills transfer directly to every memoized solution you'll ever write.
When implementing a memo cache, you have two primary options: a dictionary (hash map) or an array. Each has distinct characteristics that make it better suited for different problem types.
The choice isn't arbitrary—it depends on the structure of your state space and the operations you need.
| Characteristic | Dictionary (Hash Map) | Array |
|---|---|---|
| State representation | Any hashable type | Non-negative integers only |
| Memory allocation | Sparse: allocates only used keys | Dense: allocates entire range |
| Lookup time | O(1) average, O(n) worst case | O(1) guaranteed |
| Memory efficiency | Better for sparse state spaces | Better for dense state spaces |
| 'Not computed' check | Key existence: key in dict | Sentinel value: arr[i] == -1 |
| Multi-dimensional state | Tuple keys: (i, j, k) | Multi-dimensional array: arr[i][j][k] |
| Best for | Complex/sparse states, prototyping | Dense sequential states, performance |
Dictionary-based memoization is more general and often cleaner to implement:
if key in memoArray-based memoization is faster and more memory-predictable:
Use dictionaries when: state space is sparse, state has complex structure (strings, tuples), or you're prototyping. Use arrays when: state is dense integer-indexed, performance is critical, or you need guaranteed O(1) lookups. In interviews, dictionaries are usually fine; in production, measure before optimizing.
Let's explore dictionary-based memoization in depth. This approach is the most flexible and is often the first choice when implementing memoized solutions.
The basic pattern:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
# Pattern 1: Dictionary as function parameter (explicit)def solve_v1(n: int, memo: dict = None) -> int: """ Explicit memo parameter. Advantages: Pure function behavior, testable, clear contract Disadvantages: Caller must manage memo lifecycle """ if memo is None: memo = {} # Initialize on first call if n in memo: return memo[n] # ... compute result ... result = n * 2 # placeholder memo[n] = result return result # Pattern 2: Closure with captured dictionarydef make_solver(): """ Closure captures memo in enclosing scope. Advantages: Clean API, memo hidden from caller Disadvantages: Harder to reset or inspect memo """ memo = {} def solve(n: int) -> int: if n in memo: return memo[n] result = n * 2 # placeholder memo[n] = result return result return solve solver = make_solver()print(solver(5)) # Uses internal memo # Pattern 3: Class-based with memo as instance variableclass Solver: """ OOP approach with memo as instance state. Advantages: Method organization, easy reset, inspectable Disadvantages: More boilerplate """ def __init__(self): self.memo = {} def solve(self, n: int) -> int: if n in self.memo: return self.memo[n] result = n * 2 # placeholder self.memo[n] = result return result def reset(self): self.memo.clear() # Pattern 4: functools.lru_cache (Python-specific, recommended)from functools import lru_cache @lru_cache(maxsize=None) # None = unlimited cachedef solve_cached(n: int) -> int: """ Decorator-based memoization. Advantages: Zero boilerplate, handles hashable arguments automatically Disadvantages: Less control over cache, can't use unhashable arguments """ if n == 0: return 0 return solve_cached(n - 1) + n # Clear cache if neededsolve_cached.cache_clear()# Check cache statsprint(solve_cached.cache_info())In Python, the functools.lru_cache decorator provides automatic memoization with minimal code. For most problems—especially in interviews—it's the cleanest approach. Use @cache (Python 3.9+) for unlimited cache or @lru_cache(maxsize=N) for bounded cache.
When state maps cleanly to integer indices, arrays provide faster and more predictable performance. The key challenge with arrays is marking uncomputed states—we need a sentinel value that can't be confused with legitimate results.
Common sentinel value strategies:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
# Example: Climbing Stairs with array-based memo# Count ways to climb n stairs taking 1 or 2 steps at a time def climb_stairs(n: int) -> int: """ Array-based memoization with -1 sentinel. State: stair number (0 to n) Valid results: all positive integers Sentinel: -1 (impossible as a count) """ # Pre-allocate array of size n+1, filled with sentinel -1 memo = [-1] * (n + 1) def dp(stair: int) -> int: # Base cases if stair == 0: return 1 # One way to stay at ground if stair < 0: return 0 # Invalid: went past the stairs # Check if already computed if memo[stair] != -1: return memo[stair] # Compute: can reach this stair from stair-1 or stair-2 result = dp(stair - 1) + dp(stair - 2) # Store in memo memo[stair] = result return result return dp(n) # Example: Minimum Path Sum with None sentineldef min_path_sum(grid: list[list[int]]) -> int: """ 2D array memo with None sentinel for minimum problem. We use None because 0 could be a valid path sum, and we want to clearly distinguish "not computed" from "computed as 0". """ m, n = len(grid), len(grid[0]) # 2D memo initialized with None memo = [[None] * n for _ in range(m)] def dp(i: int, j: int) -> int: # Out of bounds if i < 0 or j < 0: return float('inf') # Infinite cost = invalid path # Base case: top-left corner if i == 0 and j == 0: return grid[0][0] # Check cache if memo[i][j] is not None: return memo[i][j] # Recursive case: min of coming from above or left result = grid[i][j] + min(dp(i - 1, j), dp(i, j - 1)) memo[i][j] = result return result return dp(m - 1, n - 1) # Example: Using float('inf') for minimum problemsdef min_coins(coins: list[int], amount: int) -> int: """ Minimum coins to make exact amount. Uses infinity as sentinel/impossible marker. """ # memo[i] = minimum coins to make amount i # Initialize with infinity (not yet computed OR impossible) memo = [float('inf')] * (amount + 1) memo[0] = 0 # Base case: 0 coins needed for amount 0 def dp(amt: int) -> int: if amt < 0: return float('inf') # Impossible # Already computed (could be valid result or still inf if impossible) if memo[amt] != float('inf') or amt == 0: return memo[amt] # Try each coin for coin in coins: sub = dp(amt - coin) if sub != float('inf'): memo[amt] = min(memo[amt], 1 + sub) return memo[amt] result = dp(amount) return result if result != float('inf') else -1 print(climb_stairs(10)) # 89print(min_path_sum([[1,3,1],[1,5,1],[4,2,1]])) # 7print(min_coins([1, 2, 5], 11)) # 3 (5+5+1)The most common bug is using -1 as sentinel when -1 is a valid result. Similarly, using 0 for count problems where 0 ways is a valid answer. Always ask: 'Can my sentinel value ever be a legitimate function result?' If yes, use None/null or a separate validity array.
Many DP problems have state defined by multiple parameters. The classic Knapsack problem, for instance, has state (item_index, remaining_capacity). For dictionaries, we need a hashable key representing this compound state.
Key design options:
| Strategy | Example | Pros | Cons |
|---|---|---|---|
| Tuple key | (i, j, k) | Clean, hashable, readable | Python-specific; JS needs string |
| String key | f'{i},{j},{k}' | Universal, works everywhere | String parsing overhead |
| Cantor pairing | i*(N+1) + j | Single integer, fast | Only for 2D, requires knowing bounds |
| Nested dict | memo[i][j] | Readable access | Must check each level exists |
| Multi-dim array | memo[i][j][k] | Cache-friendly, O(1) access | Must pre-allocate, dense only |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
# Example: 0/1 Knapsack with composite key# State: (item_index, remaining_capacity) def knapsack_dict(weights: list[int], values: list[int], capacity: int) -> int: """ 0/1 Knapsack using dictionary with tuple keys. State: (i, cap) where i = current item index, cap = remaining capacity """ n = len(weights) memo = {} # (index, capacity) -> max_value def dp(i: int, cap: int) -> int: # Base case: no items left or no capacity if i >= n or cap == 0: return 0 # Check cache with tuple key key = (i, cap) if key in memo: return memo[key] # Choice 1: Skip this item skip = dp(i + 1, cap) # Choice 2: Take this item (if it fits) take = 0 if weights[i] <= cap: take = values[i] + dp(i + 1, cap - weights[i]) result = max(skip, take) memo[key] = result return result return dp(0, capacity) def knapsack_array(weights: list[int], values: list[int], capacity: int) -> int: """ Same problem using 2D array. More efficient but requires knowing state bounds. """ n = len(weights) # 2D memo: memo[i][cap], dimensions n × (capacity+1) memo = [[-1] * (capacity + 1) for _ in range(n + 1)] def dp(i: int, cap: int) -> int: if i >= n or cap == 0: return 0 if memo[i][cap] != -1: return memo[i][cap] skip = dp(i + 1, cap) take = 0 if weights[i] <= cap: take = values[i] + dp(i + 1, cap - weights[i]) result = max(skip, take) memo[i][cap] = result return result return dp(0, capacity) # Three-dimensional state example: Edit Distancedef edit_distance(s1: str, s2: str) -> int: """ Edit distance with @lru_cache (cleanest approach). State: (i, j) where i, j are indices into s1, s2. """ from functools import lru_cache @lru_cache(maxsize=None) def dp(i: int, j: int) -> int: # Base cases: one string exhausted if i == 0: return j # Insert j characters if j == 0: return i # Delete i characters # If characters match, no operation needed if s1[i - 1] == s2[j - 1]: return dp(i - 1, j - 1) # Try insert, delete, replace return 1 + min( dp(i, j - 1), # Insert dp(i - 1, j), # Delete dp(i - 1, j - 1) # Replace ) return dp(len(s1), len(s2)) # Testweights = [2, 3, 4, 5]values = [3, 4, 5, 6]capacity = 5print(f"Knapsack (dict): {knapsack_dict(weights, values, capacity)}") # 7print(f"Knapsack (array): {knapsack_array(weights, values, capacity)}") # 7print(f"Edit distance 'kitten' -> 'sitting': {edit_distance('kitten', 'sitting')}") # 3Your memo key must encode all information that affects the result. If dp(3, 5) can return different values depending on some hidden state, your key is incomplete. A correct key uniquely identifies each distinct subproblem.
Proper initialization prevents subtle bugs and ensures your memoization works correctly. Here are the key patterns to follow:
def f(memo={}) shares the dict across calls! Use memo=None then memo = memo or {}.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
# WRONG: Mutable default argument (common Python pitfall!)def broken_memo(n: int, memo: dict = {}) -> int: """ BUG: The empty dict is created ONCE at function definition, not on each call. All calls share the same dict! """ if n in memo: return memo[n] result = n * 2 memo[n] = result return result # After multiple calls, memo persists unexpectedly # CORRECT: None default with initializationdef correct_memo(n: int, memo: dict = None) -> int: """ Create fresh dict on each top-level call. This is the standard Python memoization pattern. """ if memo is None: memo = {} if n in memo: return memo[n] result = n * 2 memo[n] = result return result # CORRECT: Pre-populate base cases in array memodef fib_with_base_cases(n: int) -> int: """ Initialize base cases directly in the memo array. Simplifies the recursive function. """ if n <= 1: return n # Pre-allocate with base cases set memo = [-1] * (n + 1) memo[0] = 0 memo[1] = 1 def dp(i: int) -> int: if memo[i] != -1: return memo[i] memo[i] = dp(i - 1) + dp(i - 2) return memo[i] return dp(n) # Pattern for problems requiring memo reset between test casesclass Solution: """ Leetcode-style class with memo reset per test. """ def solve(self, n: int) -> int: # Fresh memo per call - no contamination between tests memo = {} return self._dp(n, memo) def _dp(self, n: int, memo: dict) -> int: if n in memo: return memo[n] if n <= 1: return n memo[n] = self._dp(n - 1, memo) + self._dp(n - 2, memo) return memo[n]In Python, writing def f(memo={}) creates the dict ONCE at function definition time. Every call shares the same dict! This is one of the most common Python bugs. Always use def f(memo=None) and then if memo is None: memo = {}.
Different languages offer different levels of built-in support for memoization. Here are the idiomatic approaches for major languages:
Python offers the most elegant memoization support through decorators:
123456789101112131415161718192021222324252627282930
from functools import lru_cache, cache # Python 3.9+: @cache for unlimited memoization@cachedef fib(n: int) -> int: if n <= 1: return n return fib(n - 1) + fib(n - 2) # Python 3.2+: @lru_cache for configurable memoization@lru_cache(maxsize=1000) # LRU eviction when cache exceeds sizedef solve(n: int, k: int) -> int: # Multiple arguments work automatically if n == 0: return k return solve(n - 1, k) + solve(n - 1, k - 1) # Clear cache if neededfib.cache_clear() # Access cache statisticsinfo = fib.cache_info()print(f"Hits: {info.hits}, Misses: {info.misses}") # For unhashable arguments (lists), convert to tuples@cachedef solve_with_tuple(items: tuple, target: int) -> int: # Convert list to tuple when calling: # solve_with_tuple(tuple(my_list), target) passWhen memoization goes wrong, it can produce subtle bugs that are hard to trace. Here are common issues and how to debug them:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
# Debugging technique: Add logging to trace cache behaviordef debug_memo(n: int, memo: dict = None, depth: int = 0) -> int: """ Instrumented memoization to trace cache behavior. Use this pattern when debugging memo issues. """ if memo is None: memo = {} indent = " " * depth # Log: cache check if n in memo: print(f"{indent}CACHE HIT: n={n} -> {memo[n]}") return memo[n] print(f"{indent}COMPUTING: n={n}") # Base case if n <= 1: print(f"{indent}BASE CASE: n={n} -> {n}") return n # Recursive case result = debug_memo(n - 1, memo, depth + 1) + debug_memo(n - 2, memo, depth + 1) print(f"{indent}STORING: n={n} -> {result}") memo[n] = result return result # Common bug: Incomplete key# WRONG - ignores 'k' parameter in keydef wrong_dp(n: int, k: int, memo: dict = None) -> int: if memo is None: memo = {} # BUG: Key should be (n, k), not just n! if n in memo: # Wrong! return memo[n] # ... different k values give different results # but we're returning cached result from wrong k result = n * k memo[n] = result return result # CORRECTdef correct_dp(n: int, k: int, memo: dict = None) -> int: if memo is None: memo = {} key = (n, k) # Correct: capture all state if key in memo: return memo[key] result = n * k memo[key] = result return result # Test the debug versionprint("Tracing fibonacci(5):")debug_memo(5)When memo gives wrong results: (1) Verify key captures all state affecting result, (2) Check sentinel doesn't collide with valid values, (3) Ensure memo is fresh for each test case, (4) Add logging to trace hits vs computes, (5) Test base cases in isolation.
We've covered the practical mechanics of implementing memoization caches. Here are the essential takeaways:
What's next:
With memo implementation mastered, we'll explore how memoization avoids recomputation at a deeper level—understanding the structure of subproblem dependencies and how caching transforms the computation graph from a tree to a DAG.
You now have comprehensive knowledge of memo implementation: dictionary vs array approaches, key design, initialization patterns, language-specific idioms, and debugging strategies. These skills apply to every memoized solution you'll write.