Dynamic Programming

The core idea: overlapping subproblems + optimal substructure#

Dynamic programming (DP) applies whenever a problem has two properties:

• Overlapping subproblems — a naive recursive approach ends up solving the exact same smaller subproblem repeatedly, as the recursion page demonstrated with naive Fibonacci (fib(3) gets recomputed from scratch multiple times while computing fib(5)).
• Optimal substructure — the best solution to the whole problem can be assembled directly from the best solutions to its subproblems.

When both hold, DP's central trick is simple to state: solve each unique subproblem exactly once, store the result, and reuse it every time it's needed again instead of recomputing it. If that sounds familiar, it should — it's exactly the memoization idea already introduced on the recursion page, just formalized and applied deliberately as a strategy in its own right, alongside a second style (tabulation) for achieving the same effect without recursion at all.

Top-down (memoization) vs bottom-up (tabulation)#

The recursion page already solved Fibonacci with memoization, so this page uses a different but structurally identical problem to show both DP styles side by side: climbing stairs. You can climb 1 or 2 steps at a time — how many distinct ways are there to reach step n?

Worth noticing immediately: ways(n) = ways(n-1) + ways(n-2), with base cases ways(0) = 1 and ways(1) = 1 — the exact same recurrence as Fibonacci, just wearing a different problem's clothes. Recognizing that two differently-worded problems share the same underlying recurrence is a big part of what practicing DP actually trains.

Top-down: memoization#

def climb_stairs_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n <= 1:                          # base case: 0 or 1 step left — exactly one way
        return 1
    if n in cache:
        return cache[n]

    cache[n] = climb_stairs_memo(n - 1, cache) + climb_stairs_memo(n - 2, cache)
    return cache[n]

print(climb_stairs_memo(5))   # 8

Building up by hand: ways(0)=1, ways(1)=1, ways(2)=ways(1)+ways(0)=2, ways(3)=ways(2)+ways(1)=3, ways(4)=ways(3)+ways(2)=5, ways(5)=ways(4)+ways(3)=8. This version starts from n and recurses downward toward the base cases, caching each unique subproblem's result the first time it's computed — the same technique already used for Fibonacci, just retargeted at a new problem, which is precisely the point: once you recognize a problem's recurrence, the memoization pattern transfers over directly.

Bottom-up: tabulation#

Tabulation builds the answer from the base cases upward, in a plain loop, filling in a table of subproblem answers with no recursion at all.

def climb_stairs_tabulation(n):
    if n <= 1:
        return 1

    table = [0] * (n + 1)
    table[0], table[1] = 1, 1                 # base cases

    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]   # build each answer from the two before it

    return table[n]

print(climb_stairs_tabulation(5))   # 8

Filling the table: table = [1, 1, ?, ?, ?, ?], then table[2]=table[1]+table[0]=2, table[3]=table[2]+table[1]=3, table[4]=table[3]+table[2]=5, table[5]=table[4]+table[3]=8 — same answer, same total work, computed forward instead of backward.

Both run in O(n) time and O(n) space, a massive improvement over naive recursion's O(2ⁿ). The trade-offs between the two styles: top-down often reads more naturally (it mirrors the problem's own recursive definition) and only computes subproblems that are actually needed for the specific input, but pays a small per-call overhead for the recursive function calls and risks Python's recursion depth limit on very large n. Bottom-up has no recursion at all, so no stack-depth risk, and is typically a little faster in practice thanks to no per-call overhead — and it opens the door to a further optimization: since climb_stairs only ever needs the previous two values, not the whole table, the space can be trimmed to O(1):

def climb_stairs_optimized(n):
    if n <= 1:
        return 1

    prev2, prev1 = 1, 1                 # table[0], table[1]
    for i in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

print(climb_stairs_optimized(5))   # 8

This O(1)-space trick is possible whenever a subproblem only ever depends on a small, fixed number of previous subproblems — not every DP problem allows it, but it's always worth checking for once a working tabulation solution exists.

A classic DP problem, solved in full: 0/1 knapsack#

Problem: given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, choose a subset of items that maximizes total value without exceeding the capacity. It's called "0/1" because each item is either fully taken or left behind entirely — no partial items, no taking an item twice.

Why this needs DP: brute force would try every possible subset of items — 2ⁿ possibilities, clearly too slow to scale. The overlapping-subproblems signal here is that many different subsets, at some point in the decision process, end up asking the identical question: "given this much capacity left and these items still available, what's the best I can do?" The optimal-substructure signal: for any single item, the best overall answer is simply the better of two choices — include this item (gaining its value, spending its weight from the remaining capacity) or exclude it (leaving capacity untouched) — each choice reducing to a smaller version of the exact same problem.

def knapsack(weights, values, capacity):
    n = len(weights)
    # table[i][c] = the best value achievable using only the first i items, with capacity c
    table = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            table[i][c] = table[i - 1][c]                      # option 1: skip this item
            if weight <= c:                                     # option 2: take this item (if it fits)
                table[i][c] = max(table[i][c], value + table[i - 1][c - weight])

    return table[n][capacity]


weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack(weights, values, capacity=5))   # 7  ->  take the weight-2 and weight-3 items (values 3 + 4)

Here's the fully filled table for that exact call (rows are "items considered so far," columns are "capacity budget," and each cell is the best value achievable with that many items and that much capacity):

Reading a couple of the more interesting cells: at row 2 (items 1 and 2 available), c=5: skipping item 2 leaves table[1][5]=3; taking item 2 (weight 3, value 4) leaves 5 - 3 = 2 capacity, which item 1 alone already fills for a value of 3 (from table[1][2]), so taking it gives 4 + 3 = 7 — better than skipping, so table[2][5] = 7. At row 4, c=5: taking the weight-5 item would use the entire capacity for a value of only 6, worse than the 7 already achievable without it — so the table correctly keeps 7, meaning the optimal knapsack never even includes the heaviest, most valuable-looking item, purely because it doesn't leave room for a better combination.

The final answer sits in the bottom-right corner, table[4][5] = 7, achieved by skipping the weight-5 item entirely and taking the weight-2 and weight-3 items together (total weight 5, total value 3 + 4 = 7).

This runs in O(n × capacity) time and space — worth naming explicitly as pseudo-polynomial, since the cost depends on the actual numeric value of capacity, not just the count of items n. That means knapsack can get slow if capacity is a huge number, even with very few items — a genuinely different scaling concern than the input-count-based complexities seen elsewhere in this course. (As with climbing stairs, the table can also be compressed to a single 1D array of size capacity + 1, iterating c from high to low — a common follow-up optimization once the two-dimensional version is working correctly.)

Common mistakes#

• Forgetting or misplacing base cases — failing to initialize table[0][*] (or table[*][0]) correctly produces confidently wrong answers with no error raised.
• Not recognizing overlapping subproblems in the first place — jumping straight to a brute-force recursive solution without pausing to ask "am I about to solve this exact smaller problem more than once?"
• Getting the recurrence relation subtly wrong — an off-by-one between i and i - 1 in the knapsack table (mixing up "items considered so far" with "the current item's own index") is a classic source of quietly incorrect results.
• Applying DP to a problem that lacks optimal substructure. Not every problem qualifies — forcing a DP table onto a problem where subproblem solutions don't actually combine into a valid overall solution produces an answer that looks plausible but is wrong.
• Choosing tabulation for a state space that's mostly unreachable for the actual input, wasting memory computing table cells that are never needed — when only a small subset of subproblems will actually be visited, top-down memoization can be the more efficient choice.