Tabulation is typically faster due to better cache locality and no recursion overhead. However, memoization may avoid computing irrelevant subproblems entirely if the recursive call graph doesn't reach all states. For problems like "find path from A to B in a DAG," memoization only explores reachable nodes, while tabulation computes all table entries.

Ask these questions: Can you enumerate all subproblems easily? Is the subproblem graph acyclic? Do you need subset enumeration? Yes to all → tabulation likely better. Is recursion more natural to reason about? Is the state space sparse? Is stack overflow not a concern? → memoization.

Optimal substructure: the optimal solution to a problem can be constructed from optimal solutions of its overlapping subproblems. This means whichever approach you choose (memoization or tabulation), computing subproblems first guarantees they're correct when a later problem depends on them. Without this property, DP doesn't apply.

Yes. Memoization incurs recursion overhead for function calls, hash map lookups, and potential stack frame allocation. Tabulation uses tight iterative loops with array indexing, which is cache-friendly and avoids function call overhead. For problems where all subproblems must be solved anyway, tabulation is almost always faster. Memoization wins only when the subproblem graph is sparse enough that many states are never reached.

@functools.lru_cache is Python's built-in memoization decorator. It wraps a function with a dictionary-based cache keyed by arguments. It supports a maxsize parameter to limit memory (LRU eviction). For DP problems, it provides O(1) cache lookup on average and eliminates the need to manually manage a cache dictionary. However, it doesn't help with stack overflow from deep recursion, so tabulation may still be preferred for large inputs.

Problems with exponential or infinite state spaces are unsuitable. Examples: subset sum with large target values (2^n subsets), traveling salesman (n! permutations), and games with branching moves. Tabulation would allocate impossibly large tables. Memoization only explores reachable states, making it viable for problems with large theoretical state spaces but sparse practical reachability.

Memoization → Tabulation: (1) Identify state variables and their ranges. (2) Create a multidimensional array sized by those ranges. (3) Order subproblems bottom-up so dependencies are computed before they're used. (4) Fill the table iteratively. Tabulation → Memoization: (1) Define a recursive function with the same state parameters. (2) Add a memo cache. (3) Write base cases (table initial values). (4) Replace table lookups with recursive calls wrapped in cache checks.

Hybrid approaches are useful when: (a) Some subproblems are best solved iteratively while others benefit from lazy evaluation, (b) The DP dimension is partially bounded — tabulate the known dimension, memoize the sparse one, (c) Memory is constrained — use tabulation for a base table and memoization for extensions, (d) Algorithm like "M on the fly" which starts with a small table and grows as needed.

Python's default recursion limit is 1000, meaning memoization fails for inputs requiring deeper recursion. This makes tabulation the safer choice for production systems with unbounded input sizes. You can increase the limit via sys.setrecursionlimit(), but this risks stack overflow crashes and isn't portable. For interview problems, state the recursion limit concern and propose tabulation as the production-ready alternative.

Memoization is a specific form of caching where every recursive function result is cached, tied to the function's pure input-output mapping. General caching (e.g., Redis, HTTP caching) may cache partial results, use eviction policies, or cache side-effectful operations. Memoization assumes: (a) the function is pure (same input → same output), (b) all results are cached indefinitely (no eviction), (c) the cache exists for the lifetime of a single top-level computation.

Memoization follows the recursive call graph — the order of computation is determined by which subproblems the recursion actually reaches. Tabulation follows the dependency graph you define by iterating in a fixed order. For debugging, this difference is significant: in memoization, a missing base case causes a stack overflow with no clear picture of which states were hit; in tabulation, you can inspect any table entry immediately. When something goes wrong with a memoized solution, you often need to add logging to the cache lookup/store logic to reconstruct which states were actually visited.

With a hash map (typical for memoization), space is O(k) where k is the number of reachable states — often much less than the full state space. Each cache entry has overhead from the hash map bucket structure. With tabulation using a dense array, space is O(n) for an n-state DP table with no per-entry overhead, but you pay for entries you never use. For problems with sparse reachable states (like a DAG where only a subset of nodes are reachable), memoization can be asymptotically better in practice due to this difference.

In memoization, the recursion naturally gives you the call stack. You can augment each cached result with a "parent pointer" — storing which subproblem led to this result. Then reconstruction is a simple walk from the final state back through parent pointers. In tabulation, the table already contains all subproblem values; reconstruction typically involves working backwards from the final cell, consulting the table to decide which direction to step at each point. Both approaches need O(path length) extra space for reconstruction.

Neither standard memoization nor tabulation handles cycles directly, because DP fundamentally requires a DAG (no cycles) to guarantee termination and optimal substructure. For cyclic dependencies, you have two options: (a) break the cycle by fixing a starting point or (b) use iterative relaxation (like Bellman-Ford) which runs for a fixed number of iterations and gradually converges — this is essentially tabulation with a "iterations" outer loop. Memoization alone will infinite-loop on a cycle unless you add cycle-detection or a depth limit.

Hash map lookups in memoization are O(1) average but have poor cache locality — each lookup may miss the CPU cache and hit main memory. Tabulation's array indexing is O(1) with excellent cache locality (contiguous memory access). For problems where you end up visiting most states anyway, tabulation's dense array is typically faster overall despite computing some unused entries. The crossover point depends on cache hit rate, hash function cost, and how "spread out" your memoization keys are. On modern CPUs, cache locality can easily swing performance by 2–5x in favor of tabulation for dense workloads.

In languages like Python and JavaScript, memoization caches hold references to all computed results. If the cache grows unbounded, it becomes a memory leak — especially for DP problems with large keys (strings, tuples). Solutions include: using a bounded cache (LRU via @functools.lru_cache(maxsize=N)), clearing the cache after the computation, or switching to a WeakMap (in JavaScript) so entries can be garbage collected when no other references exist. Tabulation doesn't have this problem because the table is typically stack-allocated or scoped to a function and released immediately after use.

"M on the fly" (sometimes called "semi-memoization" or "lazy tabulation") starts with a small table and grows it dynamically as new states are needed — it computes table entries on demand like memoization but stores them like tabulation. The practical benefit: you get the sparse memory usage of memoization with the iteration speed and cache friendliness of tabulation once a table entry is computed. A real-world use case is online DP where future inputs aren't known upfront but the algorithm can reuse previously computed results as they arrive.

Tabulation fills the table in a known order, so you can often reduce space by keeping only the rows or columns currently needed. The classic example is the 0/1 knapsack problem where O(nW) space reduces to O(W) by iterating backwards and overwriting previous rows. Memoization can't easily do this because you don't know which states will be needed next — the recursive call order is unpredictable. If a memoized solution needs space optimization, you typically need to redesign the recurrence or switch to tabulation entirely.

Many advanced DP formulations still use memoization as the underlying mechanism even when the state space is complex. For example, Altered DP changes a recurrence during computation (sometimes based on intermediate results) — memoization naturally handles this because each state is computed exactly once on first access. Similarly, DP over a segment tree (for range queries in LIS or other problems) typically uses memoization to cache segment tree node results, since not all nodes are visited in a flat segment tree traversal. The memoization layer is often invisible — handled by a data structure's internal caching rather than explicit user code.

For production code, the decision hierarchy is: (1) If input size is bounded and known to be small, prefer whichever is clearer — usually memoization mirrors the problem statement more directly. (2) If input size can be large (10,000+), prefer tabulation to avoid stack overflow. (3) If you need the recursion-like call structure but want to avoid the call stack, use an explicit stack — this is essentially iterative memoization with manual state management. For library code that others will call with unpredictable input sizes, tabulation is the conservative default. Always measure: the performance difference is rarely dramatic unless you hit stack limits or cache thrashing.