From recursion to dynamic programming

You've written a recursive function, it passes the small example, and the interviewer asks what happens when n is 500. A strong answer gives the exact reason the plain version is slow, then fixes it in steps without starting over: remember each answer the first time you compute it, then fill those answers into a table, then keep only the part of the table you still read. Solving each smaller version once and building bigger answers from the stored ones is called dynamic programming. This lesson walks one problem through every step, so you can repeat the walk on a problem you haven't seen.

Hear the recursion in the prompt

A problem is recursive when, after you make the first choice, what is left is the same question on a smaller input. The wording usually gives it away:

• "How many ways" or "how many different" asks for a count, and counts add up over the possible first choices.

• "Fewest", "cheapest", "longest" or "most" over a run of decisions asks for the best result over the possible first choices.

• "Is it possible" asks whether any first choice leads to a yes.

• "Return the answer modulo 1,000,000,007" signals a count too big for 64 bits, which almost always comes from exponentially many objects counted by a recurrence.

Here is the problem this lesson carries. A night guard starts in a museum's lobby. Every minute he walks through exactly one door into a neighboring room; he never stays put. How many different routes of exactly n moves end back in the lobby? The museum has four rooms:

The first choice is the first door. After it, the guard stands in some room with n - 1 moves left, facing the same question: how many routes from here end in the lobby?

Define the answer from smaller answers

Before code, say in one sentence what a call means: routes(room, k) is the number of routes of exactly k moves that start in room and end in the lobby. The arguments that change between calls, room and k, are the state: the smallest set of values that decides the rest of the answer. Two rules complete the definition.

• The base case answers the smallest input without recursing. With zero moves left the guard is done, so routes(room, 0) is 1 if room is the lobby and 0 otherwise.

• The transition builds one answer from smaller ones. Every route leaves through some door, so routes(room, k) is the sum of routes(nxt, k - 1) over each room nxt one door away.

def count_routes(doors, start, end, n):
    """Routes of exactly n moves from start to end, one door per move."""
    def routes(room, moves_left):
        if moves_left == 0:
            return 1 if room == end else 0
        return sum(routes(nxt, moves_left - 1) for nxt in doors[room])

    return routes(start, n)


museum = {
    "lobby": ["north", "south"],
    "north": ["lobby", "south", "cafe"],
    "south": ["lobby", "north", "cafe"],
    "cafe": ["north", "south"],
}
print(count_routes(museum, "lobby", "lobby", 4))  # 10

Test the base case on its own: from the lobby with n = 0 the answer is 1 (the route that goes nowhere), and from the cafe it is 0. Every other answer is built from that value, so if it returned 0 for the lobby, every count would come out 0.

Recursion also costs memory. A call waits for its children, so the longest chain of waiting calls puts n + 1 frames on the call stack: O(n) space before you store anything. Python caps that stack at 1,000 frames by default (sys.getrecursionlimit()), and each level here uses two, one for routes and one for the generator inside sum(). On Python 3.13 the memoized version in the next section raises RecursionError at n = 499. Lesson 6 shows how to trade the call stack for an explicit one; the table later in this lesson removes the problem.

Some recursive problems stop at this stage. A search for one valid arrangement rarely meets the same partial arrangement twice, so storing answers buys nothing; the speed there comes from abandoning a partial answer the moment it breaks a rule. Everything below pays off only when the same smaller question gets asked more than once.

Draw the call tree before you speed anything up

To see whether questions repeat, draw the calls for routes(lobby, 3), each under the call that made it:

• routes(lobby, 3)

  • routes(north, 2)

    • routes(lobby, 1)

    • routes(south, 1)

    • routes(cafe, 1)

  • routes(south, 2)

    • routes(lobby, 1)

    • routes(north, 1)

    • routes(cafe, 1)

routes(lobby, 1) and routes(cafe, 1) each run twice, and the undrawn level below holds 14 calls spread over only four rooms. Repeats are the signal. Each call branches at most d ways, where d is the largest number of doors out of any one room, and the tree is n levels deep, so the plain version makes O(d^n) calls for d of 2 or more. Lesson 1 covers reading a runtime off a tree like this. In this museum the count grows about 2.6 times per extra move: 17,241 calls for n = 10 and 1,900,623 for n = 15, though n = 15 allows only 4 × 16 = 64 different (room, k) pairs.

Memoization, or top-down dynamic programming, stores each state's answer the first time it is computed and returns the stored answer on every later call. The recursion stays as it was; a dict wraps it:

def count_routes_memo(doors, start, end, n):
    memo = {}  # (room, moves_left) -> number of routes

    def routes(room, moves_left):
        if moves_left == 0:
            return 1 if room == end else 0
        key = (room, moves_left)
        if key not in memo:
            memo[key] = sum(routes(nxt, moves_left - 1) for nxt in doors[room])
        return memo[key]

    return routes(start, n)

To get the cost, count the states and multiply by the work per state. There are at most R(n + 1) states, where R is the number of rooms. Computing one reads its room's door list once, so one value of k costs O(R + E) across all rooms, where E is the number of doors. Time is O(n(R + E)), and space is O(nR) for the memo plus O(n) for the stack. That counts each addition as one step; interviewers usually ask for the count modulo 1,000,000,007, which keeps every number small enough for that to hold.

@functools.cache on the inner function does the same bookkeeping in one line, with a fresh cache per outer call. The version that goes wrong is a top-level function that takes memo={} as a default argument: Python creates that dict once, when it defines the function, and every later call shares it. The interviewer runs your second test, a different museum, and gets answers left over from the first. A key that leaves out part of the state fails just as quietly: memoize on room alone, and every later call for the lobby gets back the first lobby answer stored, whatever its k.

Fill a table, smallest k first

Memoization starts from the big question and lets the calls find the small ones. A table, or bottom-up dynamic programming, runs the other way: compute every k = 0 answer, then every k = 1 answer from those, and so on up. The one rule for the order is that every value a cell reads must already be filled. Row k reads only row k - 1, so increasing k works.

def count_routes_table(doors, start, end, n):
    # table[k][room] = routes of exactly k moves from room to end
    table = [{room: int(room == end) for room in doors}]
    for k in range(1, n + 1):
        below = table[k - 1]
        row = {}
        for room in doors:
            row[room] = sum(below[nxt] for nxt in doors[room])
        table.append(row)
    return table[n][start]

Time and space match the memoized version, O(n(R + E)) and O(nR), but no call nests inside another, so n = 5,000 runs where the recursion crashed. The table also fills states the recursion would never visit: harmless here, but on a problem where most states are unreachable, top-down can be the faster of the two.

In an interview, start top-down: it is the recursion you already explained plus a dict. Move to the table when the interviewer asks about very large n or about memory, because the table is where the next saving comes from.

Keep only the row you still read

Look at what the loop reads. Row k uses row k - 1 and nothing older, so every row below that is dead weight.

def count_routes_rolling(doors, start, end, n):
    prev = {room: int(room == end) for room in doors}  # k = 0
    for _ in range(n):
        cur = {room: sum(prev[nxt] for nxt in doors[room]) for room in doors}
        prev = cur
    return prev[start]

Space drops from O(nR) to O(R), and time stays O(n(R + E)). The general move is to find the oldest value any update reads and keep only that much: one previous row here, two if each row read the two before it, and O(1) space when each answer reads a fixed number of single earlier values.

The trap is updating a single dict in place, writing row[room] = sum(row[nxt] ...) inside a loop over rooms. By the time a room is summed, some of its neighbors already hold their new values, so it mixes k - 1 answers with k answers. The interviewer sees the museum's count for n = 2 come out 0 instead of 2. Building cur in full before prev moves avoids it.

Say the state and transition out loud

Before any code, say what one call means, the base case, the transition and the cost that follows from the number of states. It takes twenty seconds and lets the interviewer fix the idea before you spend ten minutes coding it.

"Let routes(room, k) be the number of k-move routes from room that end in the lobby. With no moves left it's 1 in the lobby and 0 anywhere else. Otherwise I add up routes(next, k - 1) over the rooms one door away. That's R times (n + 1) states, each reading its own doors, so O(n(R + E)) once I memoize, and after that I can drop to one row of R values."

When a rule depends on where the route has already been, the state must carry whatever the rule needs to remember. Suppose the route must pass through the cafe at least once. routes(room, k) can no longer tell whether reaching the lobby counts, so the state grows to (room, seen_cafe, k), where seen_cafe turns true on entering the cafe and the base case counts the lobby only when it is true: two states per room for each k, at most 2R(n + 1). Say that growth out loud too. It shows you chose the state on purpose.

The mistake interviewers see most is a table written before that sentence exists: indices shuffled around with nothing saying what table[k][room] means. When the output is wrong, neither of you can tell whether the idea failed or the typing did.

Practicing with these questions

For each question on this page, write the meaning of one call, the base case and the transition before any code, and time how long that takes; if it runs past three minutes, the state is probably missing something. Then go only as far through the four versions as the question needs, and say each version's cost as you reach it. Start with Cheapest Daily Shirt Colors With No Color Repeated on Consecutive Days and say your state sentence aloud before you type. The Blind 75 dynamic programming set has more problems for the same drill.