Back to Study Material Data Structures and Algorithms

Memoization

Memoization is the top-down approach to dynamic programming: write a recursive function that solves the problem naturally, then add a cache (memo table) to...

Memoization

Top-Down DP with Memoization

Memoization is the top-down approach to dynamic programming: write a recursive function that solves the problem naturally, then add a cache (memo table) to store results of sub-problems the first time they are computed. On subsequent calls with the same arguments, return the cached result immediately instead of recomputing.

The structure is simple: before computing, check if the answer is already in the cache; if yes, return it; if no, compute recursively, store the result in the cache, then return it. In Python, the @functools.lru_cache decorator automates this for simple cases. In Java or C++, you typically use a HashMap or a 2D array indexed by the function arguments.

A worked example: the coin change problem asks for the minimum number of coins from a given set that sum to a target amount T. A recursive definition: min_coins(T) = 1 + min over all coins c of min_coins(T - c), for T - c >= 0. Without memoization, this has exponential time complexity because the same sub-amounts are computed repeatedly. With memoization, each unique sub-amount is computed once, giving O(T * n) time where n is the number of coin denominations, and O(T) space for the cache.

Memoization has a natural advantage over tabulation: it only computes sub-problems that are actually needed. If large parts of the state space are unreachable from the original problem, memoization skips them automatically while tabulation fills the entire table regardless.

Interview tip: If recursion depth might exceed the call stack limit (Python's default is 1000 frames), mention that you would either increase the recursion limit for the given input size or switch to the iterative tabulation approach. Showing awareness of practical constraints distinguishes strong candidates.

Cache Design and Eviction Strategies

Choosing the right cache data structure for memoization significantly affects both performance and memory usage. For small integer arguments, a pre-allocated array or 2D array provides O(1) lookup with minimal overhead. For large or sparse state spaces, a hash map (unordered_map in C++, HashMap in Java, dict in Python) is more memory-efficient but adds hashing overhead per lookup.

For multi-parameter functions, you need a composite key. In Python, a tuple of arguments works naturally as a dictionary key. In C++, you can either flatten multi-dimensional indices into a single integer (key = i * (maxJ + 1) + j) or use a map with a pair key. Flattening is faster because it avoids hash computation for complex structures.

Cache eviction becomes relevant when the total number of distinct sub-problems is very large. LRU (Least Recently Used) eviction keeps a fixed-size cache and discards the least recently accessed entry when the cache is full. This trades a potential cache miss (and recomputation) for reduced memory use. Python's lru_cache(maxsize=N) implements this automatically.

For competitive programming, where all sub-problems must be solved, full memoization with no eviction is standard. For real systems, such as memoizing API responses or computed properties, LRU or TTL-based eviction is necessary to prevent unbounded memory growth.

Sentinel values signal that a cache entry has not yet been computed. Common choices are -1 for problems where the answer is non-negative, None in Python, or a separate boolean array indicating whether each entry is populated. Never use 0 as a sentinel if 0 is a valid answer — this is a frequent source of subtle bugs.

Interview tip: If you use -1 as a sentinel but the problem allows negative answers, your memoization will be incorrect. Always choose a sentinel that falls outside the valid answer range, and state this choice explicitly when explaining your approach.

Memoization vs. Tabulation Trade-offs

Memoization (top-down) and tabulation (bottom-up) are two implementations of the same DP idea. Understanding when to choose each is an important practical skill. Memoization is often easier to write correctly because it directly mirrors the recursive problem definition. Tabulation is often faster in practice because it avoids function call overhead and is more cache-friendly due to sequential memory access.

Memoization advantages: natural recursion structure, computes only needed sub-problems, easier to extend with additional constraints, and code is closer to the mathematical definition. Memoization disadvantages: function call overhead for each sub-problem, potential stack overflow for deep recursion, and less predictable memory access patterns (hash map lookups scatter across memory).

Tabulation advantages: iterative loops are faster than recursive calls, sequential array access patterns maximize CPU cache utilization, no stack overflow risk, and space optimization (rolling array) is straightforward. Tabulation disadvantages: you must determine the correct fill order, you compute all sub-problems even unused ones, and the code is sometimes less intuitive.

A concrete performance difference: for the longest common subsequence of two strings of length 1000, tabulation fills a 1000x1000 array sequentially, which is cache-friendly. Memoization with a hash map performs 1,000,000 hash lookups scattered across memory, which causes frequent cache misses. In benchmarks, tabulation is typically 3-5x faster on large inputs for this reason.

For tree-structured problems (like tree DP, where each node's answer depends only on its children), memoization is more natural because the access pattern is already tree-shaped and tabulation requires a topological sort.

Interview tip: Offer both approaches if time permits, implement one, and explain the trade-off. Saying "I will implement bottom-up tabulation here because the sub-problem space is dense and I want to avoid recursion overhead" demonstrates maturity beyond just knowing that DP exists.