Memoization vs Tabulation — Top-Down vs Bottom-Up DP in Java

Memoization is top-down

• Recursive
• Starts from the original problem
• Breaks into subproblems
• Caches each result the first time computed

Tabulation is bottom-up

• Iterative
• Starts from base cases
• Builds up to the original problem
• Fills a table in dependency order

Same asymptotic complexity — both are O(states × work).

Memoization — top-down

Style

• Recursive function with cache check at the start
• If cached, return; else compute and store
• HashMap for complex state, array for integer-indexed

Pros

• Often shorter, mirrors the math
• Only computes states actually visited (sparse-friendly)
• Iteration order handled automatically by recursion
• Easier to write first, easier to derive

Cons

• Recursion overhead (stack frames, function call cost)
• Worse cache locality (heap allocations, pointer chasing)
• HashMap overhead if used
• Stack overflow risk for deep recursion (~10K frames default)
• Harder to apply space optimization

When memoization wins

• Sparse subproblem space (chess endgames)
• Complex iteration order (DP on DAG, game theory)
• Quick prototyping
• State isn't naturally array-indexed

Tabulation — bottom-up

Style

• Allocate a table (array or 2D array)
• Initialize base cases
• Iterate in dependency order, filling each cell

Pros

• 2–5× faster in practice (no recursion, better cache, no HashMap)
• No stack overflow risk
• Space optimization easy (rolling arrays)
• More predictable performance
• JIT optimizes loops better than recursion

Cons

• Must figure out iteration order manually
• Computes all states even if not all are needed
• Slightly more verbose
• Can't handle complex state spaces as cleanly

When tabulation wins

• Dense subproblem space (all states will be computed)
• Performance matters (hot path, large n)
• Need space optimization (long sequences, large grids)
• Recursion depth would overflow
• Iteration order is clear (nested loops)

Concrete example — Fibonacci

Naive recursion: O(2^n), ~1 trillion calls for fib(40)

Memoization: O(n) calls, ~50 ns/call — fib(40) in microseconds

• Stack overflow at fib(10000)

Tabulation O(n) space: O(n) iterations, ~5 ns/iter — fib(40) in ~250 ns

• No stack issues

Tabulation O(1) space (rolling): same time, just two variables

int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
    int curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
}

• Best version for production

Why tabulation is faster (constant-factor)

1. 1
   No recursion overhead — single stack frame, loop variables
2. 2
   Better cache locality — sequential array access; CPU prefetcher loves it
3. 3
   No HashMap overhead — array indexing is single-cycle
4. 4
   JIT loop optimization — vectorization, unrolling, bounds-check elimination
5. 5
   No null/sentinel checks — every dependency is already computed

Common pitfalls

Memoization

• Forgetting to memoize — still exponential
• Wrong sentinel value (using 0 when 0 is a valid answer)
• Stack overflow at depth ~10K
• String keys in HashMap (slow) — use long encoding

Tabulation

• Wrong iteration order (state computed before its dependencies)
• Off-by-one in array sizes
• Forgetting to initialize base cases
• Not noticing space-optimization opportunities

Hybrid approach

• Write memoization first — verifies recurrence
• Profile or estimate — if performance matters, convert to tabulation
• Apply rolling-array optimization if memory is tight

Edge cases

Deep recursion needed?

• Increase stack: -Xss16m
• Or convert to tabulation

Sparse states?

• Memoization
• Tabulation wastes space on uncomputed cells

Need space optimization?

• Tabulation with rolling array
• Memoization can't easily reduce cache size

Recommendation: Both styles compute the same answer in the same asymptotic time, so picking is about trade-offs and context. For interviews, either is acceptable — write whichever you can derive faster (often memoization), then explain you could convert to tabulation for performance. For production, prefer tabulation when the state space is dense and performance matters — it's typically 2–5× faster, has no stack-overflow risk, and unlocks rolling-array space optimization (O(n) → O(1) for many problems). Use memoization when the state space is sparse (you only visit a fraction of possible states), the iteration order is complex (DP on DAG or game-theory minimax), or you're prototyping. Beware Java's stack depth limit (~10K frames) — deep recursion will throw StackOverflowError unless you increase -Xss or convert to iteration. The hybrid workflow is best: write memoization to verify the recurrence (fewer bugs), then convert to tabulation if profiling demands. Avoid String keys in memoization HashMaps (slow hashing); encode (i, j) as a long instead. The mental model: memoization explores; tabulation enumerates. Memoization follows recursion's natural order; tabulation requires you to explicitly design the iteration order, but rewards you with raw speed and predictable memory.