Adding a Memo Dictionary/Ar… — Memoization — Top-Down… | OneNoughtOne

0/97

Data Structures & AlgorithmsMemoization — Top-Down DP

Memoization — Top-Down Dynamic Programming

LevelIntermediate

Duration60 mins

TopicMemoization — Top-Down DP

2 / 4

Adding a Memo Dictionary/Array

The Engineering of Memory

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.

What You Will Learn

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.

Two Approaches — Dictionary vs Array

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.

Dictionary vs Array Memoization
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: Works with any hashable arguments (tuples, strings, integers) Naturally handles sparse state spaces (only visited states consume memory) Easy to check if a value has been computed: if key in memo Slightly more overhead due to hashing Array-based memoization is faster and more memory-predictable: Works when state can be mapped to integer indices Requires pre-allocation of the entire state space Uses sentinel values (-1, None, \infty) to mark uncomputed states Lower constant factors, better cache locality

When to Choose Each

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.

Dictionary-Based Implementation

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:

dict_memo_patterns.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# 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 dictionary
def 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 variable
class 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 cache
def 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 needed
solve_cached.cache_clear()
# Check cache stats
print(solve_cached.cache_info())

Python's @lru_cache Is Your Friend

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.

Array-Based Implementation

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:

Sentinel Value Strategies

•-1 for non-negative results — Works when all valid results are ≥ 0
•None/null for object types — Natural uncomputed marker in many languages
•Positive infinity for minimum problems — Initialize with MAX_VALUE, any computed result is smaller
•Negative infinity for maximum problems — Initialize with MIN_VALUE, any computed result is larger
•Separate boolean array — memo[i] stores result, computed[i] stores whether it's valid (uses 2x memory)

array_memo_patterns.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 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 sentinel
def 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 problems
def 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))   # 89
print(min_path_sum([[1,3,1],[1,5,1],[4,2,1]]))  # 7
print(min_coins([1, 2, 5], 11))  # 3 (5+5+1)

Sentinel Value Pitfalls

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.

Designing Composite Keys for Multi-Dimensional State

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:

Composite Key Design Strategies
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

composite_keys.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
# 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 Distance
def 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))
 
 
# Test
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(f"Knapsack (dict): {knapsack_dict(weights, values, capacity)}")  # 7
print(f"Knapsack (array): {knapsack_array(weights, values, capacity)}")  # 7
print(f"Edit distance 'kitten' -> 'sitting': {edit_distance('kitten', 'sitting')}")  # 3

Key Design Rule of Thumb

Your 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.

Initialization Patterns and Best Practices

Proper initialization prevents subtle bugs and ensures your memoization works correctly. Here are the key patterns to follow:

Initialization Checklist

•Size the memo correctly — For array-based: ensure dimensions cover all valid states. Off-by-one errors (n vs n+1) are common.
•Choose appropriate sentinel — Match to your result type: -1 for non-negative ints, None for objects, infinity for min/max problems.
•Handle base cases explicitly — Either check in the recursive function or pre-populate in the memo. Don't mix approaches inconsistently.
•Avoid mutable default arguments — In Python, def f(memo={}) shares the dict across calls! Use memo=None then memo = memo or {}.
•Consider clearing between tests — Static/global memos persist. Clear before each test case to avoid contamination.

initialization_patterns.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# 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 initialization
def 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 memo
def 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 cases
class 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]

The Mutable Default Argument Bug

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 = {} .

Language-Specific Idioms and Decorators

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:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from functools import lru_cache, cache
 
# Python 3.9+: @cache for unlimited memoization
@cache
def 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 size
def 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 needed
fib.cache_clear()
 
# Access cache statistics
info = fib.cache_info()
print(f"Hits: {info.hits}, Misses: {info.misses}")
 
# For unhashable arguments (lists), convert to tuples
@cache
def solve_with_tuple(items: tuple, target: int) -> int:
    # Convert list to tuple when calling:
    # solve_with_tuple(tuple(my_list), target)
    pass

Debugging Memoization Issues

When memoization goes wrong, it can produce subtle bugs that are hard to trace. Here are common issues and how to debug them:

Common Memoization Bugs

•Incomplete key — Key doesn't capture all state that affects the result. Different subproblems map to the same key, returning wrong cached values.
•Sentinel collision — Using -1 as sentinel when -1 is a valid result. Legitimate -1 values are treated as 'not computed'.
•Shared mutable state — Memo dictionary persists across test cases or function calls when it shouldn't.
•Mutable arguments in key — Using a list as a dict key (unhashable) or using an object that changes after being keyed.
•Wrong base case — Base case returns incorrect value, and since it's cached, the error propagates through all dependent subproblems.
•Stack overflow — Recursion depth exceeds limit before memoization can help (usually on first computation).

debugging_memo.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Debugging technique: Add logging to trace cache behavior
def 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 key
def 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
 
 
# CORRECT
def 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 version
print("Tracing fibonacci(5):")
debug_memo(5)

Debugging Strategy

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.

Data Structures & AlgorithmsMemoization — Top-Down DP

Memoization — Top-Down Dynamic Programming

LevelIntermediate

Duration60 mins

TopicMemoization — Top-Down DP

2 / 4

Adding a Memo Dictionary/Array

The Engineering of Memory

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.

What You Will Learn

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.

Two Approaches — Dictionary vs Array

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.

Dictionary vs Array Memoization
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: Works with any hashable arguments (tuples, strings, integers) Naturally handles sparse state spaces (only visited states consume memory) Easy to check if a value has been computed: if key in memo Slightly more overhead due to hashing Array-based memoization is faster and more memory-predictable: Works when state can be mapped to integer indices Requires pre-allocation of the entire state space Uses sentinel values (-1, None, \infty) to mark uncomputed states Lower constant factors, better cache locality

When to Choose Each

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.

Dictionary-Based Implementation

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:

dict_memo_patterns.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# 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 dictionary
def 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 variable
class 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 cache
def 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 needed
solve_cached.cache_clear()
# Check cache stats
print(solve_cached.cache_info())

Python's @lru_cache Is Your Friend

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.

Array-Based Implementation

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:

Sentinel Value Strategies

•-1 for non-negative results — Works when all valid results are ≥ 0
•None/null for object types — Natural uncomputed marker in many languages
•Positive infinity for minimum problems — Initialize with MAX_VALUE, any computed result is smaller
•Negative infinity for maximum problems — Initialize with MIN_VALUE, any computed result is larger
•Separate boolean array — memo[i] stores result, computed[i] stores whether it's valid (uses 2x memory)

array_memo_patterns.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# 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 sentinel
def 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 problems
def 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))   # 89
print(min_path_sum([[1,3,1],[1,5,1],[4,2,1]]))  # 7
print(min_coins([1, 2, 5], 11))  # 3 (5+5+1)

Sentinel Value Pitfalls

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.

Designing Composite Keys for Multi-Dimensional State

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:

Composite Key Design Strategies
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

composite_keys.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
# 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 Distance
def 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))
 
 
# Test
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(f"Knapsack (dict): {knapsack_dict(weights, values, capacity)}")  # 7
print(f"Knapsack (array): {knapsack_array(weights, values, capacity)}")  # 7
print(f"Edit distance 'kitten' -> 'sitting': {edit_distance('kitten', 'sitting')}")  # 3

Key Design Rule of Thumb

Your 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.

Initialization Patterns and Best Practices

Proper initialization prevents subtle bugs and ensures your memoization works correctly. Here are the key patterns to follow:

Initialization Checklist

•Size the memo correctly — For array-based: ensure dimensions cover all valid states. Off-by-one errors (n vs n+1) are common.
•Choose appropriate sentinel — Match to your result type: -1 for non-negative ints, None for objects, infinity for min/max problems.
•Handle base cases explicitly — Either check in the recursive function or pre-populate in the memo. Don't mix approaches inconsistently.
•Avoid mutable default arguments — In Python, def f(memo={}) shares the dict across calls! Use memo=None then memo = memo or {}.
•Consider clearing between tests — Static/global memos persist. Clear before each test case to avoid contamination.

initialization_patterns.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# 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 initialization
def 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 memo
def 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 cases
class 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]

The Mutable Default Argument Bug

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 = {} .

Language-Specific Idioms and Decorators

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:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from functools import lru_cache, cache
 
# Python 3.9+: @cache for unlimited memoization
@cache
def 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 size
def 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 needed
fib.cache_clear()
 
# Access cache statistics
info = fib.cache_info()
print(f"Hits: {info.hits}, Misses: {info.misses}")
 
# For unhashable arguments (lists), convert to tuples
@cache
def solve_with_tuple(items: tuple, target: int) -> int:
    # Convert list to tuple when calling:
    # solve_with_tuple(tuple(my_list), target)
    pass

Debugging Memoization Issues

When memoization goes wrong, it can produce subtle bugs that are hard to trace. Here are common issues and how to debug them:

Common Memoization Bugs

•Incomplete key — Key doesn't capture all state that affects the result. Different subproblems map to the same key, returning wrong cached values.
•Sentinel collision — Using -1 as sentinel when -1 is a valid result. Legitimate -1 values are treated as 'not computed'.
•Shared mutable state — Memo dictionary persists across test cases or function calls when it shouldn't.
•Mutable arguments in key — Using a list as a dict key (unhashable) or using an object that changes after being keyed.
•Wrong base case — Base case returns incorrect value, and since it's cached, the error propagates through all dependent subproblems.
•Stack overflow — Recursion depth exceeds limit before memoization can help (usually on first computation).

debugging_memo.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Debugging technique: Add logging to trace cache behavior
def 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 key
def 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
 
 
# CORRECT
def 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 version
print("Tracing fibonacci(5):")
debug_memo(5)

Debugging Strategy

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.

Adding a Memo Dictionary/Array

The Engineering of Memory

Two Approaches — Dictionary vs Array

Dictionary-Based Implementation

Array-Based Implementation

Designing Composite Keys for Multi-Dimensional State

Initialization Patterns and Best Practices

Language-Specific Idioms and Decorators

Debugging Memoization Issues

There’s more to understand.

Adding a Memo Dictionary/Array

The Engineering of Memory

Two Approaches — Dictionary vs Array

Dictionary-Based Implementation

Array-Based Implementation

Designing Composite Keys for Multi-Dimensional State

Initialization Patterns and Best Practices

Language-Specific Idioms and Decorators

Debugging Memoization Issues

There’s more to understand.