Dynamic programming: the idea

Why we need it: the same work, again and again

In Module 5 you met the plain recursive Fibonacci function. fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) again, and so on. The same calls repeat so often that the time grows like O(2ⁿ): fib(40) makes hundreds of millions of calls. Yet there are only 41 different questions (fib(0) to fib(40)). The waste is in answering the same question many times.

Dynamic programming, or DP, is the cure: answer each different question once, store the answer, and look it up the next time. The name is old and a little misleading ("programming" here meant "planning with a table"); think of it as "careful recursion with a notebook".

Two signs that DP fits

• Overlapping subproblems: the problem breaks into smaller problems of the SAME kind, and the same smaller problems come up many times. Merge sort also splits a problem, but its halves never repeat, so storing answers would not help.
• Optimal substructure: the best answer to the big problem can be built from the best answers to smaller problems. The cheapest way to reach step 10 must come through the cheapest way to reach step 9 or step 8.

Top-down and bottom-up

Top-down DP (memoisation) is the recursive function you already know, plus a dictionary or functools.cache that remembers results. You start from the big question and let the recursion ask the smaller ones. It is easy to write from a recurrence, and it only solves the subproblems you actually need.

Bottom-up DP (tabulation) fills a table, usually a list called dp, from the smallest questions upwards with a loop. There is no recursion, so no RecursionError for large n and no function-call overhead. It also makes the order of work clear, which is what lets you save space later.

A four-step recipe

1. State: say in words what dp[i] means. "dp[i] = the number of ways to reach step i." If you cannot say it in one sentence, you are not ready to code.
2. Recurrence: how dp[i] is built from smaller states. Think about the LAST choice: the last move to step i was a 1-step from i − 1 or a 2-step from i − 2, so dp[i] = dp[i − 1] + dp[i − 2].
3. Base cases: the smallest states you know without thinking. dp[0] = 1 (one way to stand still at the bottom) and dp[1] = 1.
4. Order and answer: fill the table so every state you read is already filled (here i from 2 up to n), then say which cell is the answer (dp[n]).

def climb_stairs(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print([climb_stairs(n) for n in range(6)])   # Output: [1, 1, 2, 3, 5, 8]

Saving space: keep only what you read

dp[i] reads only dp[i − 1] and dp[i − 2], so the rest of the table is never needed again. Keep two variables and slide them forward. Time stays O(n), space drops from O(n) to O(1). Interviewers often ask for this as a follow-up.

def climb_stairs(n):
    a, b = 1, 1          # ways(i - 2), ways(i - 1)
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(climb_stairs(10))   # Output: 89

A min-cost version

In "min cost climbing stairs", cost[i] is what you pay to step off stair i, you may start on stair 0 or stair 1, and each move goes up 1 or 2 stairs. The top is just past the last stair. State: dp[i] = the cheapest cost to stand on position i. Recurrence: dp[i] = min(dp[i − 1] + cost[i − 1], dp[i − 2] + cost[i − 2]). Base cases: dp[0] = dp[1] = 0, because you may start there for free. Answer: dp[n]. For cost = [10, 15, 20] the answer is 15: start on stair 1, pay 15 and jump 2 to the top.

Common mistakes

• Coding before you can state dp[i] in words. Fix: write the state as a comment first; most DP bugs are a fuzzy state.
• Wrong or missing base cases, for example dp[0] = 0 for counting problems. Fix: check the smallest inputs (n = 0, 1, 2) by hand against your table.
• Filling in the wrong order, so you read a cell that is still 0. Fix: make sure every cell on the right side of the recurrence is filled before the one on the left.
• Table off by one: a list of size n when you need index n. Fix: use size n + 1 when the answer is dp[n].
• Memoising with a mutable default argument or a global dict that keeps old answers between test cases. Fix: create the cache inside the function, or use functools.cache on an inner function.