Memoization (Top-Down)
Memoization keeps the recursive formulation but adds a cache so each reachable state is computed at most once.
Cache and Recurse
Memoization is top-down DP. You ask for the original answer, let recursion discover the states it needs, and store each computed state in a cache. When another path asks for the same state, the function returns immediately.
This style is especially natural when the recurrence is easiest to express as decisions from the current state. It keeps the code close to the mathematical definition, which is useful for interval DP, string DP, and problems where not every theoretical state is reachable.
Choosing the Cache Key
The cache key must include every parameter that can change the answer. If the answer depends on index and remaining capacity, cache index + capacity, not just index. If it depends on two string prefixes, cache both prefix lengths. If it depends on whether the previous item was taken, that flag belongs in the state.
A missing state variable creates incorrect cache hits. An unnecessary state variable creates too many states and may hide overlap. The best memoized solutions are precise: enough information for correctness, no history that the future no longer needs.
When to Prefer Memoization
Use memoization when the recursive recurrence is much clearer than the iterative order, when reachable states are sparse, or when you need to prototype correctness quickly. It is also strong for DFS-shaped DP, such as Word Break over starting indices or graph-like state spaces with pruning.
The trade-off is recursion overhead and stack depth. Java can hit stack limits on very deep linear recurrences. Memoization can also be slightly slower than tabulation because of function calls, hash maps, or sentinel checks, but clarity often wins during the first correct implementation.
Pros and Cons
The main advantage is directness. The code mirrors the recurrence and computes only states that are actually requested. Base cases are usually local and readable.
The main disadvantages are operational. Deep recursion can overflow the stack, cache initialization needs care, and hash-based keys can add overhead. For production-style interview answers, mention that the same recurrence can often be converted to bottom-up tabulation if stack depth or constants matter.
Memoized one-dimensional recurrence
The recursive function parameters define the state. For a two-dimensional DP, use a two-dimensional array or a map key that includes both state variables.
Key Takeaways
- Memoization is top-down DP: recursion plus a cache keyed by state.
- Every variable that can change the answer must be part of the cache key.
- Memoization is often the clearest first correct solution, especially when reachable states are sparse.
- Watch for recursion depth, cache sentinels, and extra overhead from hash-based keys.