Memoization (Top-Down DP with a Cache)

Top-down DP stores (args)->value in a hash map—@lru_cache in Python. Same DAG as bottom-up but explores lazily.

Why this shows up in the real world

Autocomplete tries share suffix memo tables. Parsing CFG memoizes nonterminals.

Core idea (explained for students)

Write recursive def with hashable args; add modulo wrapper for counting.

Try this in Python

def fib(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]


print(fib(30))

Common mistakes

• Unhashable list arguments—convert to tuple.
• Python recursion limit on deep chains.

Key takeaways

• sys.setrecursionlimit only as last resort—prefer iterative if stack deep.