Unit 5.2 · about 3 h
120 / 324Memoization, tabulation and dependency order
Memoized recursion dies near depth 1000 in CPython. Tabulation with an explicit order is the form that survives production-sized inputs.
- implement
You can now
- Implement memoized and tabulated forms of one recurrence and show they compute the same values.
- Read dependencies off a recurrence and state the evaluation order before writing the loop.
- Predict when memoized recursion hits the Python recursion limit and switch to tabulation.
Covers
- Dependency order and topological evaluation
- Memoized recursion and state identity
- Bottom-up tabulation and iteration order
Study, in this order
3 steps
- Fibonacci from naive recursion to iterationAlgorithms - dynamic programming
Section 3.1 (pp. 97-102):
RecFibo, the \(T(n) = 2F(n+1) - 1\) call-count argument,MemFibo,IterFiboandIterFibo2Depth · Skip Section 3.2, the matrix-squaring speedup (p. 103), until the limits unit.
- The four-step conversion to a tableDSA Handbook - dynamic programming
The four-step conversion: dependency DAG, topological order, loop, array; Tracing the table fill on \(n = 8\)
- The default 1000-frame limitPython sys: recursion limit
sys.getrecursionlimitandsys.setrecursionlimit: the limit guards the C stack, and the highest safe value is platform-dependent. Check the current value withsys.getrecursionlimit()(1000 on CPython 3.13).
Focus on
- Memoization visits states lazily in recursion order; tabulation visits them eagerly in an order you choose. Both compute the same values.
- The dependency DAG must be acyclic. For \(\operatorname{fib}(i)\) the edges run to smaller indices, so increasing \(i\) is a valid topological order.
- A Python frame per index means depth-\(n\) recursion needs a limit above \(n\). Set it once at module top level, never per function.
- State count times per-state work gives total time: \(O(n)\) states at \(O(1)\) each is \(O(n)\) for Fibonacci.
Reproduce closed-book
fib. Both give \(\operatorname{fib}(25) = 75025\). At the default limit of 1000, \(\operatorname{fib}(2500)\) raises RecursionError; with the limit raised once to 10000 the memoized form returns a 523-digit integer, and the tabulated form returns the same digits. Assert the two results are equal.Traps
- Reusing one global memo across calls for state that is not absolute. Stale entries from the previous call return wrong answers; build a fresh memo per call.
- Returning a mutable object from a memoized function and letting the caller mutate it. Later cache hits return the mutated object.
- Copying a top-down recurrence into a bottom-up loop without flipping the direction. A left-to-right loop reading \(\text{dp}[i+1]\) reads uninitialized cells.
Practice
LeetCode 509 - Fibonacci Number
Implement memoized and tabulated forms; check \(n = 2, 3, 4\) (answers 1, 2, 3), then submit.
Compare both forms on \(n = 30\). After submitting, use the DSA Handbook dp-recursion-to-memo ladder as the reference.
LeetCode 1137 - N-th Tribonacci Number
Extend the window to three predecessors; check \(n = 4\) (answer 4) and \(n = 25\) (answer 1389537), then submit.
Carry three rolling values in the tabulated form. After submitting, compare with the DSA Handbook fixed look-back section.
Self-test
-
\(\operatorname{fib}(2500)\) under the default limit: what happens and why?
RecursionError. The chain runs 2500 frames deep before the first base case returns, and the default limit is 1000. The cache cannot help because no call has returned yet. -
When is tabulation better than memoization if both are \(O(n)\)?
When the topological order is obvious and the input is deep or call overhead matters. Tabulation has no recursion stack and pays one index per step instead of one frame per state. -
Your bottom-up loop reads \(\text{dp}[i+1]\) left to right and returns garbage. What went wrong?
The loop order violates the dependency direction. Either iterate right to left or rewrite the recurrence so it reads already-filled cells. -
Why must a memoized function be pure?
The cache swaps recomputation for lookup. If the result depends on hidden mutable state, the stored value is stale for the next call and the answer changes.
Completion criterion
Stop when
Both forms agree on \(\operatorname{fib}(25) = 75025\) from a blank file, and you can state the order and the limit behavior without notes.
Mark passed, then open 5.3 Only mark this when you can do it without notes.Leads to
- 5.3 Solution reconstruction and rolling state Keep the table when you must reconstruct; compress only the value.
- 5.4 Sequence and string dynamic programming Apply both evaluation forms to two-index recurrences.
Comes after
- 5.1 Dynamic programming states, transitions and base casesFill the recurrence by memo or by table once the state is fixed.
Resources for this unit
- DSA Handbook - dynamic programming Study Part 9 in order from state and recurrence through sequence, grid, tree and bitmask families. For every example, close the page and reconstruct the state, transition and evaluation order.
- Algorithms - dynamic programming Use the dynamic-programming chapter to derive states and recurrences from first principles and to separate DP from greedy reasoning and shortest paths.
- Python sys: recursion limit Read
sys.getrecursionlimitandsys.setrecursionlimit: the limit guards the C stack and its safe maximum is platform-dependent. Check the default withgetrecursionlimit(1000 on CPython 3.13), raise it once for memoized DP, or switch to tabulation for deep inputs.
Also in this section
- AlgoMaster DSA - dynamic programming slice Attempt Coin Change, Longest Common Subsequence and House Robber III cold. Write the state, transition, base case and evaluation order first; compare against brute force on small inputs and reconstruct a witness when available.
- Hypothesis - exhaustive and differential DP tests Generate small valid instances, compare memoized, tabulated and exhaustive results, and retain shrunk failures for wrong state, base case, order and compression defects.
- NeetCode - unseen mixed problems Use two tag-hidden mixed problems as the final transfer test. One must require rejecting a tempting greedy or insufficient-state solution with a counterexample.
- Erickson lecture note D - Advanced Dynamic Programming Read Section D.1 (Saving Space: Divide and Conquer) for the Hirschberg Half-table split that recovers an optimal edit sequence in \(O(m + n)\) space.
- Erickson lecture note J - Approximation Algorithms Read Section J.1 (Load Balancing) for the Partition reduction that makes exact scheduling NP-hard, the
GreedyLoadBalanceheuristic, and Theorem J.1 with its factor-2 proof.