Memoization turns exponential recursive brute force into polynomial time by caching subproblem results, but the mechanics of how you cache differ sharply across languages — from Python's one-line decorator to Java, Go, and JavaScript's fully manual map management. This section is about wiring up correct, fast caching and dodging the classic table-initialization and key-encoding bugs that plague DP code specifically, not about which subproblems to define.
Language Verdict: Pros, Cons & Recommendation
@cache/lru_cache memoize any recursive function with a single line — zero manual cache wiring or check-then-put logic- Tuples are natively hashable, so multi-parameter state keys (
(i, j)) need no encoding step at all - No boxed-object identity trap —
== on cached int results is always a value comparison regardless of magnitude - Tuple assignment (
prev, curr = curr, prev) makes space-optimized rolling-array swaps a single readable line
lru_cache/@cache requires every argument to be hashable — a list or dict argument raises TypeError and must be normalized to a tuple first- CPython's default ~1000-frame recursion limit is the tightest of the three languages, so a long top-down DP hits
RecursionError before Java or JS would fail
new int[m+1][n+1] allocates genuinely independent rows — no row-aliasing bug to guard against, unlike Python's/JS's naive fill-based initrecord Pair(int i, int j) (Java 16+) gives a clean, correctly-hashed multi-param memo key with generated equals/hashCode- Tolerates deeper recursion than Python before
StackOverflowError, giving more headroom for top-down DP over long inputs - Primitive
Map<Integer,Long>-style tables and arrays keep memoized state allocation-light versus general object graphs
- No memoization decorator or annotation at all — every recursive function needs a hand-declared
Map plus explicit check-then-put boilerplate Map<Integer,Integer> returns boxed Integers; comparing cached values with == silently breaks once a result falls outside the -128..127 cache range- No tuple type or destructuring swap — multi-param keys need manual pairing-encoding (or an extra
record allocation), and rolling-array swaps need a temp variable
map[[2]int]int is a real pair-key memo — arrays of ints are comparable, no string join or record typeprev, curr = curr, prev swaps rolling-row headers in one line, like Python- A named
var dfs func(...) closure plus a captured memo map is a clean top-down pattern make per row makes the 2D table aliasing bug harder to hit than Python's [[0]*n]*n
- No
@cache decorator — every recursive function needs a hand-declared map plus comma-ok lookup - Missing map keys return
0, a valid DP result — if memo[k] != 0 is a real cache-miss bug; always comma-ok - No default-dict; 2D tables need a loop of
make([]int, n+1) or the inner rows stay nil and panic
- Array-destructuring (
[prev, curr] = [curr, prev]) gives Python-like rolling-array swap ergonomics without a temp variable Array.from({length}, factory) cleanly avoids the row-aliasing bug, mirroring Python's list-comprehension fix- A higher-order
memoize(fn) wrapped around a Map is a reusable, easy-to-read pattern once written - Numbers are never boxed, so there's no Java-style identity-vs-equality footgun when comparing cached values
- No memoization decorator and no value-based tuple/record key —
Map keys objects/arrays by reference, so structurally-identical state silently misses the cache with no error at all - Multi-param state must be joined into a delimited string key by hand, with real risk of ambiguous-join collisions (
"1","23" vs "12","3") - No transparent
@cache-style wrapping — the recursive function must explicitly call the outer memoized binding, an easy-to-miss wiring detail
Recommendation: Lean on Python's @cache/lru_cache for effortless memoization — still the typical DSA default. Go is a solid nice-to-have (map[[2]int]int, rolling-row tuple swap) if you remember comma-ok. Java and JS need a hand-rolled Map cache. Watch for Java's boxed-Integer == bug, JS's reference-keyed Map missing equal states, and fall back to bottom-up tabulation when recursion depth is a risk.
Coding Mechanics, Side by Side
Python is the only language with a built-in memoization decorator; Java, Go, and JS require you to manage a cache object by hand alongside (or inside) the recursive function.
from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
# older Python, or when you need a bounded cache:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib2(n):
return n if n < 2 else fib2(n - 1) + fib2(n - 2)
@cache (3.9+) is sugar for @lru_cache(maxsize=None) — both wrap the function in a transparent cache keyed on the exact argument tuple, with zero manual bookkeeping. lru_cache(maxsize=None) disables eviction entirely (unbounded cache); pass a real maxsize if you want LRU eviction instead. This is unambiguously the cleanest of the three languages for top-down DP — you write the plain recursive definition and get memoization for free.
Python's automatic caching comes with a real restriction — every argument must be hashable — while Java, Go, and JS's manual caches sidestep the restriction differently (Java's List is hashable by value, Go arrays of comparable types are comparable, JS's Map keys by reference either way).
from functools import cache
@cache
def solve(state):
...
solve([1, 2, 3])
# TypeError: unhashable type: 'list'
# Fix: pass an immutable, hashable tuple instead
@cache
def solve(state: tuple):
...
solve((1, 2, 3)) # works
lru_cache/@cache hash every argument to build the cache key, so any mutable, unhashable argument (a list, dict, or set) raises TypeError: unhashable type at call time. The standard fix is to normalize multi-dimensional or collection state into a tuple (or frozenset) before the memoized call — tuples are hashable natively as long as their contents are hashable too.
Once a recursive function depends on more than one parameter (e.g. two indices i, j), each language has its own idiom for combining them into a single cache key — cross-reference the Hash Maps & Sets section for the general custom-key techniques these all borrow from.
memo = {}
def solve(i, j):
if (i, j) in memo:
return memo[(i, j)]
# ... compute result ...
memo[(i, j)] = result
return result
A tuple (i, j) is hashable natively and reads exactly like the mathematical state it represents — no encoding step needed. This is the standard manual-memo idiom when you don't (or can't) use @cache, e.g. when the function also takes an unhashable parameter that must be excluded from the key.
A Java-specific footgun that shows up specifically in memoized DP code: comparing two cached Integer results with == works by accident for small values and silently breaks for larger ones.
memo = {}
memo[1] = 200
memo[2] = 200
a = memo[1]
b = memo[2]
print(a == b) # True -- int == is always a value comparison, regardless of magnitude
print(a is b) # implementation detail, irrelevant here -- never use `is` for value checks
Python has its own small-int cache (-5..256, an implementation detail), but it's irrelevant to this bug because == on int is always a value comparison — there's no boxed-object identity trap lurking behind it the way there is in Java. As long as you use == (never is) to compare memoized values, Python has no equivalent footgun to watch for.
The single most common DP-table bug: initializing every row by replicating one row reference instead of creating a fresh row each time. Cross-reference the Arrays & Dynamic Arrays section for the general form of this bug — here's the DP-flavored version that corrupts an entire edit-distance-style table.
# BUG: every row is the SAME list object
m, n = 4, 5
dp = [[0] * (n + 1)] * (m + 1)
dp[0][1] = 1
print(dp[1][1]) # 1 -- wrong! row 1 was never touched, but it IS row 0
# FIX: a fresh row per iteration
dp = [[0] * (n + 1) for _ in range(m + 1)]
dp[0][1] = 1
print(dp[1][1]) # 0 -- correct, rows are independent
Identical failure mode to the general array aliasing bug, but here it silently corrupts an entire edit-distance/LCS-style table: every dp[i][j] = ... assignment appears to update only row i, but since all rows alias the same list, the whole table converges to one shared row and produces wrong answers for every cell that assumed row independence. Always build DP tables with a list comprehension (for _ in range(...)), never [[...]] * n.
A near-universal tabulation idiom, independent of language: size your DP array n + 1 (or (m+1) x (n+1) for 2D) so that index 0 represents "zero items/characters considered" as a real, addressable base case, rather than needing to special-case negative indices.
# Python: dp[i] = best answer using the first i items
dp = [0] * (n + 1)
dp[0] = 0 # base case: zero items considered
for i in range(1, n + 1):
dp[i] = dp[i - 1] + arr[i - 1] # arr is 0-indexed, dp is 1-indexed
// Java: identical convention, same off-by-one shift between dp[] and arr[]
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + arr[i - 1];
}
// Go: make zeros the slice; same 1-indexed dp vs 0-indexed arr shift
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
dp[i] = dp[i-1] + arr[i-1]
}
// JavaScript: same shape again
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + arr[i - 1];
}
The mechanical trade-off is identical everywhere: you gain a clean base case and never write if (i - 1 < 0) guards, at the cost of a permanent one-off indexing shift between the 0-indexed source array/string and the 1-indexed dp array that you must track carefully through every access (arr[i - 1], not arr[i]).
Collapsing a 2D table to O(n) or O(1) space is a mechanical rewrite, not an algorithmic one — the syntax for "swap current and previous row" (or iterating backwards for a 0/1-knapsack-style in-place update) differs across languages.
# Two-row rolling swap
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
curr[j] = prev[j] + prev[j - 1]
prev, curr = curr, prev # cheap tuple-swap, no temp variable needed
# 1D in-place, iterated backwards (0/1 knapsack style)
dp = [0] * (capacity + 1)
for weight, value in items:
for c in range(capacity, weight - 1, -1):
dp[c] = max(dp[c], dp[c - weight] + value)
prev, curr = curr, prev swaps two names in one step via tuple packing/unpacking — no temporary variable, and no actual data copy since only references move. For the 1D in-place case, range(capacity, weight - 1, -1) walks backwards so each dp[c] update still reads a not-yet-updated (i.e. "previous row") value from dp[c - weight], which is what makes reusing a single array safe here.
Brief cross-reference to the Trees & Recursion Mechanics section's full treatment of call-stack limits — worth a specific callout here because top-down DP over a long linear input (e.g. a string of length 10,000) is one of the most common ways interview code actually hits it.
import sys
from functools import cache
@cache
def edit_distance(i, j):
# deep recursion over a 10,000-char string easily exceeds
# CPython's default ~1000-frame recursion limit
...
sys.setrecursionlimit(20_000) # last-resort workaround; risks a raw segfault, not a catchable error
Python is by far the most likely of the three to fail first here — its default recursion limit (~1000 frames) is a hard frame count, not a memory bound, so a memoized recursion over a long string can raise RecursionError well before Java or JS would hit their own (memory-based) stack limits. sys.setrecursionlimit is a real but risky escape hatch (see Trees & Recursion Mechanics for why raising it too far can crash the interpreter instead of raising a catchable error); the more robust interview answer is converting the memoized recursion to an equivalent bottom-up (tabulation) loop, which has no call-stack cost at all.