Lesson

DP: From Recursion to a Table

Picture a staircase

You're standing in front of a staircase with n steps. Each move takes you up 1 or 2 steps. How many different ways can you get to the top?

Start from the end. You reach the last step n in one of two ways:

a 1-step move from step n-1;
a 2-step move from step n-2.

So the number of ways to reach n equals the number of ways to reach n-1 plus the number of ways to reach n-2:

ways(n) = ways(n-1) + ways(n-2)

You've just split one big problem into two smaller ones. All of dynamic programming rests on this move.

The two signs of DP

Optimal substructure. The answer to the big problem is built from answers to small ones. The answer for n is made of the answers for n-1 and n-2, and you don't need to know anything else.

Overlapping subproblems. The same small problems come up again and again. Look at the call tree for n = 5:

Call tree of ways(5): ways(3) is computed twice, ways(2) three times

ways(3) is computed twice, ways(2) three times. At n = 40 there would be millions of repeats, and naive recursion runs in O(2^n).

If a problem has both signs, you're almost certainly looking at DP.

The four-step path

Step	Idea	Time	Space
1. Recursion	compute straight from the formula	`O(2^n)`	`O(n)` stack
2. Memoization	remember what's already computed in a dictionary	`O(n)`	`O(n)`
3. Bottom-up table	fill a `dp` array from small to large	`O(n)`	`O(n)`
4. Space optimization	keep only the last two values	`O(n)`	`O(1)`

Memoization is the same recursion, but before computing anything you check your "notebook": if ways(k) has already been computed, you return the saved value right away. Each k is computed once.

The table turns the recursion upside down. Instead of descending from the top, you climb from the bottom: small answers first, then the big ones built from them. No recursion means no stack overflow.

i-2 ↓ 33

i-1 ↓ 54

i ↓ 85

136

dp[5] = dp[4] + dp[3] = 5 + 3 = 8 — each cell depends on the two before it

Notice that dp[i] only needs the two neighboring cells on its left. Everything further left will never be needed again. So the whole array can be replaced with two variables. That's space optimization.

Bottom-up table

def climb_stairs(n: int) -> int:
    # dp[i] is the number of ways to reach step i
    dp = [0] * (n + 1)
    dp[0] = 1                      # base: on the ground there's one way (stand still)
    if n >= 1:
        dp[1] = 1                  # base: one move to the first step
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # transition
    return dp[n]                   # answer

Space optimization: O(1)

def climb_stairs(n: int) -> int:
    prev2, prev1 = 1, 1            # dp[i-2] and dp[i-1]
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2   # slide the "window"
    return prev1

How it sounds in an interview

The interviewer isn't waiting for code right away; they want four clear statements. Say them out loud before you write anything:

State: "dp[i] is the number of ways to reach step i." The key is to say what a cell means.
Transition: "You can reach step i from i-1 or from i-2, so dp[i] = dp[i-1] + dp[i-2]."
Base case: "dp[0] = 1, dp[1] = 1; these are the smallest cases that don't follow from the formula."
Answer: "The answer is in dp[n]."

Then add: "That's O(n) time. Each step only looks at the two previous values, so space shrinks to O(1)." This shows right away that you understand the technique rather than remembering the problem by heart.

Stuck on an unfamiliar problem? Write an honest recursion first, add memoization, and only then convert it to a table. That path almost always gets you to a solution.

Common mistakes

A fuzzy state. "Well, dp is something about the steps" won't cut it. Without a precise meaning for a cell, you can't get the transition or the base case right.
A missing or wrong base case. If dp[0] = 0, everything becomes zero. Check the base case by hand on tiny n: for n = 2 there should be 2 ways.
Going out of bounds. For n = 0 or n = 1, accessing dp[1] or dp[i-2] can crash. Guard against it.
The wrong fill order. Fill the table so that by the time you compute dp[i], everything it needs is already computed.
Optimizing space too early. Get a working table first, then compress it. Otherwise it's easy to mix up the order of assignments.

Now you have the full path: formula, recursion, memoization, table, and compression. Next in this chapter, you'll walk that path yourself on new problems.