Skip to main content

Memoization vs Tabulation: Trade-offs

What This Concept Is​

Memoization evaluates states on demand and stores completed answers. Tabulation evaluates them in an explicit dependency-respecting order. Either style can be dense or sparse. Neither changes the mathematical recurrence; they can differ in which states they visit, stack depth, allocation, locality and lookup costs.

For finite acyclic recurrences, distinguish unseen, currently evaluating and complete states when cycles might occur. A cache entry created only after a recursive call returns cannot stop a cycle between unfinished calls.

Why It Matters Here​

The best style follows the contract and resource limits. Recursion depth can fail on a long dependency chain even with a small number of states. A dense table can allocate a huge unreachable region. Dictionary and call overhead must be measured rather than replaced by a universal "bottom-up is faster" claim.

Concrete Examples​

Stair counts. Let ways(n) count ordered compositions of n from 1 and 2. Bases are ways(0)=ways(1)=1. A safe tabulation handles the zero-sized input:

def ways(n):
    if n < 0:
        raise ValueError("negative height")
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
    return dp[n]

Unconditionally setting dp[1] would fail for n=0. Memoized recursion also computes the recurrence, but a chain of n calls can exceed a runtime's stack limit.

Actual sparsity. For exact coin totals using denominations [4,6], a top-down solver starting at an even target visits only even nonnegative remainders. Adding denomination 1 removes that sparsity argument: every smaller remainder becomes reachable. Sparse allocation is useful only after checking what the transitions reach. Represent impossible amounts distinctly from zero coins.

Cache lifetime. A local cached function may close over one fixed job list, string pair or digit bound. If it is reused after that input changes, identical keys can mean different problems. Create a new cache per problem instance, or include immutable input identity/version in the key. Caching tight digit states is valid within one fixed-bound query.

Common Confusion / Misconceptions​

  • Zero can be a completed answer. Testing if cache[state] confuses it with a cache miss; use membership or a distinct sentinel.
  • Tabulation need not sweep a full rectangular array. A topological worklist or dictionary of frontier states is also an explicit evaluation strategy.
  • Memoization does not guarantee polynomial time, eliminate stack storage, or automatically resolve cyclic recurrences.
  • A warm-cache benchmark measures a different operation from solving a new instance.

How To Use It​

Specify the fixed input and the cache key. Prove a rank decreases in recursive dependencies, or validate the dependency graph. Implement a transparent full version first. Record states evaluated, candidates considered and peak live storage, then choose whether a different layout addresses a measured bottleneck. Compare implementations on the same input and include answer reconstruction.

Check Yourself​

When can a local closure omit the entire input from its key? What makes a cache entry safe to reuse? Does a valid recurrence prevent a recursion-depth failure?

Mini Drill or Application​

Memoize exact coin count for [4,6] and targets 0, 7, 8. Compare to a bottom-up table. Feedback: 0 coins, impossible, 2 coins. Then add 1 and explain why the set of visited states and answers change; discard the old cache.

Read This Only If Stuck​

CLRS: memoized and bottom-up rod cutting. Compare the evaluated subproblems rather than treating pseudocode line counts as a performance measurement.