Memoization (Top-Down DP) and DP on DAGs

Memoization is recursion with a cache: the first time a state is solved, its answer is stored; every later call with the same arguments returns the stored value. Because every state is solved at most once, a memoized search is a full dynamic programming solution written top-down.

Intuition

Consider a 0/1 knapsack: items have a cost and a value, and you may spend at most budget. The obvious brute force tries "skip" and "take" for every item:

def best_value_bruteforce(cost: list[int], value: list[int], budget: int) -> int:
    n = len(cost)
    best = 0

    def dfs(i: int, left: int, total: int) -> None:
        nonlocal best
        if i == n:
            best = max(best, total)
            return
        dfs(i + 1, left, total)  # skip item i
        if cost[i] <= left:
            dfs(i + 1, left - cost[i], total + value[i])  # take item i

    dfs(0, budget, 0)
    return best

This is O(2^n), yet the pair (i, left) has only n * (budget + 1) possible values. The same (i, left) is reached through many different choices of earlier items, and the work below it is identical every time. The only obstacle to caching is the total accumulator: the function's behavior depends on how we got here. Rewrite it so the function returns "the best value obtainable from items i..n-1 with left budget". Now the result depends only on the arguments, so it can be cached:

from functools import cache


def best_value_memo(cost: list[int], value: list[int], budget: int) -> int:
    n = len(cost)

    @cache
    def dfs(i: int, left: int) -> int:
        # best value using items i..n-1 with `left` budget remaining
        if i == n:
            return 0
        res = dfs(i + 1, left)
        if cost[i] <= left:
            res = max(res, value[i] + dfs(i + 1, left - cost[i]))
        return res

    return dfs(0, budget)

That is the whole method:

1. Write a brute-force DFS (or write the DP recurrence directly).
2. Remove every outside variable: the function's answer must be a pure function of its parameters, which together form the state.
3. Add a cache keyed by those parameters.

When to use it in interviews / OAs

• You can already write a brute-force recursion and notice the same arguments repeating (draw the recursion tree for a small input).
• The problem has a natural "from here, what is the best I can still do" formulation: a position in a string, a cell in a grid, the remaining budget, the set of used items.
• The evaluation order is awkward to express as loops: the graph of states is implicit, transitions are irregular, or only a small fraction of the states is reachable.
• You want a correct solution quickly and can optimize later if asked.

Memoization vs tabulation

The bottom-up version uses the same state and transition; it just fixes an evaluation order explicitly. Since dfs(i, ...) reads dfs(i + 1, ...), the table is filled from i = n - 1 down to 0:

def best_value_table(cost: list[int], value: list[int], budget: int) -> int:
    n = len(cost)
    # f[i][left] means exactly what dfs(i, left) means
    f = [[0] * (budget + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for left in range(budget + 1):
            f[i][left] = f[i + 1][left]
            if cost[i] <= left:
                f[i][left] = max(f[i][left], value[i] + f[i + 1][left - cost[i]])
    return f[0][budget]

	Memoization (top-down)	Tabulation (bottom-up)
Evaluation order	Found automatically by recursion	You must pick a valid order
States computed	Only reachable ones	Every cell of the table
Constant factor	Function calls and hashing	Tight loops, faster
Memory tricks	Reusing rows is awkward	Keeping only the last row or two is easy
Depth	Limited by the recursion limit	No recursion

In an interview, top-down is usually the fastest way to a correct answer: it reads like the recurrence and handles boundaries naturally. Switch to tabulation when the follow-up asks for less memory or when recursion depth becomes a problem.

DP on a DAG

Memoization works whenever the "depends on" relation between states has no cycles, i.e. the states form a DAG. Many problems become DP once you notice such a DAG.

Longest increasing path in a grid. Moving only to a strictly larger neighbor can never revisit a cell, so cells form a DAG and the answer is its longest path.

def longest_increasing_path(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0]) if grid else 0

    @cache
    def walk(r: int, c: int) -> int:
        # longest strictly increasing path that starts at (r, c)
        best = 1
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:
                best = max(best, 1 + walk(nr, nc))
        return best

    return max((walk(r, c) for r in range(rows) for c in range(cols)), default=0)

The bottom-up equivalent processes the DAG in topological order. Here that order is simply "larger values first", because every edge goes to a larger value:

def longest_increasing_path_sorted(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0]) if grid else 0
    best = [[1] * cols for _ in range(rows)]
    cells = sorted(((grid[r][c], r, c) for r in range(rows) for c in range(cols)), reverse=True)
    for v, r, c in cells:  # every larger neighbor is already final
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > v:
                best[r][c] = max(best[r][c], best[nr][nc] + 1)
    return max((max(row) for row in best), default=0)

Stacking blocks. Each block type (x, y, z) can be used any number of times in any orientation, and a block may sit on another only if both base sides are strictly smaller. "Fits on top of" is a strict relation, so orientations form a DAG; the tallest tower is the heaviest path, with each node weighted by its height.

def tallest_tower(blocks: list[tuple[int, int, int]]) -> int:
    # every block type gives 3 orientations: (short base side, long base side, height)
    shapes = []
    for x, y, z in blocks:
        for h, p, q in ((x, y, z), (y, x, z), (z, x, y)):
            shapes.append((min(p, q), max(p, q), h))

    @cache
    def best(i: int) -> int:
        # tallest tower whose bottom block is shapes[i]
        a, b, h = shapes[i]
        on_top = [best(j) for j, (c, d, _) in enumerate(shapes) if c < a and d < b]
        return h + max(on_top, default=0)

    return max((best(i) for i in range(len(shapes))), default=0)

Complexity

Time = (number of reachable states) x (work per state); space = number of cached states plus recursion depth. Knapsack: O(n * budget). Increasing path: O(rows * cols), with four neighbors per cell (the sorted version adds a log factor for sorting). Stacking: O(m^2) for m = 3n orientations.

Common pitfalls

• Hidden state: a cached function that reads an accumulator, a global or a mutated list returns wrong answers. Everything the answer depends on must be a parameter.
• Unhashable arguments: functools.cache needs hashable arguments. Pass indices, tuples or a bitmask instead of lists.
• Sentinel collisions: when using an array, do not mark "not computed" with a value that can be a real answer (for example -1 when answers can be negative). Use None.
• Stale caches: a module-level cached function keeps answers from a previous input. Define it inside the solver (as above) or call cache_clear().
• Cycles: if a state can depend on itself (moving freely in four directions, for instance), memoized recursion never terminates. That is a shortest-path problem (BFS/Dijkstra), not a DAG DP.
• Recursion depth: Python's default limit is about 1000 frames. Raise it with sys.setrecursionlimit, and for very deep chains (10^5 and more) convert to bottom-up.

Interview variations

• Index recursion: climbing stairs, decode ways, word break; the state is a position in the input.
• Grid DAGs: longest increasing path, counting paths that only move right/down.
• Containment chains: box stacking, envelope nesting, longest chain of pairs; sort or memoize over a strict "fits inside" relation.
• Games: "can the first player win from this state" with the state as a bitmask or tuple, cached as win/lose.
• Interval recursion: minimum cost to cut a stick or to merge piles, memoized on (left, right).
• Counting paths in a DAG: same memoized DFS, adding counts instead of taking a max.