Dynamic Programming: The Real Guide

The moment you knew you needed this

You wrote the Fibonacci function in five lines. It works. You test it on n = 10 — instant. Then someone runs it on n = 50 and your laptop fan spins up and the process never returns.

That's not a bug in your logic. The logic is correct. It's a shape problem — the recursion tree has a catastrophically bad shape.

Here's fib(5) expanded:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ← computed here
│   │   └── fib(1)
│   └── fib(2)     ← and again here
└── fib(3)
    ├── fib(2)     ← and again here
    └── fib(1)

fib(2) runs three times. fib(3) runs twice. By fib(50), you're doing roughly 2^50 function calls — about a quadrillion — to compute a number you could store in a long integer. Dynamic programming's entire value proposition is: you already know the answer to fib(2) — stop recomputing it.

{ "type": "recursion", "fn": "fibonacci", "n": 5, "title": "fib(5) — spot the duplicated subtrees" }

Step through this. Watch fib(2) fire three separate times. That redundancy is the problem DP solves. Everything else is bookkeeping.

The four-step framework

Before diving into specific problems, internalize this process. I apply it every time, in order:

flowchart TD
    A["1. Write brute-force recursion<br/>(correctness first)"] --> B["2. Identify repeated subproblems<br/>(draw the tree, spot duplicates)"]
    B --> C["3. Memoize top-down<br/>(add a cache, return early on hit)"]
    C --> D["4. Tabulate bottom-up<br/>(fill a table from base cases up)"]
    D --> E["5. Optimize space<br/>(if recurrence is narrow, collapse table)"]
    style A fill:#7c5cff,color:#0a0a0f
    style B fill:#7c5cff,color:#0a0a0f
    style C fill:#22d3ee,color:#0a0a0f
    style D fill:#22d3ee,color:#0a0a0f
    style E fill:#00ff9d,color:#0a0a0f

Step 5 is optional — it never changes the time complexity, only the space. But interviewers love it, and in production the difference between O(n) and O(1) memory matters when n is ten million rows.

The only real skill is defining the state correctly — and we'll make that concrete.

What "state" means (and why getting it wrong breaks everything)

The state is the minimal set of variables that uniquely identifies a subproblem. Think of it as the parameter list of your recursive function stripped of anything you can derive from context.

Ask yourself: "If I woke up mid-computation knowing only these variables, could I correctly compute the answer for this subproblem?"

• Fibonacci: state is just n. Given n, you know exactly what to compute.
• Climbing stairs: state is the current stair number.
• Grid paths: state is (row, col). You need both — knowing only row doesn't tell you where in the grid you are.
• Knapsack: state is (item_index, remaining_capacity). Remove either and you can't solve the subproblem.

Too little state → wrong answers. Too much state → table explodes. Getting this right is 80% of solving a DP problem.

Family 1: 1D linear DP

Climbing stairs

You can climb 1 or 2 steps at a time. How many distinct ways to reach step n?

Write the recursion first. To reach step n, you came from either step n-1 (took 1 step) or step n-2 (took 2 steps). So:

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

That's Fibonacci with renamed variables. Base cases: ways(0) = 1 (one way to stay at the ground), ways(1) = 1.

Memoize it (top-down):

def climb_stairs(n: int) -> int:
    memo = {}

    def dp(i):
        if i <= 1:
            return 1
        if i in memo:
            return memo[i]          # cache hit — return immediately
        memo[i] = dp(i - 1) + dp(i - 2)
        return memo[i]

    return dp(n)

One extra dictionary. Every subproblem computed exactly once. Time: O(n). Space: O(n) for the cache plus O(n) call stack.

Tabulate it (bottom-up):

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

No recursion, no call stack. Fill from left to right and you're done.

Optimize space: the recurrence only ever looks at i-1 and i-2. You don't need the whole table.

def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Now it's O(1) space. Same O(n) time. This is the finished solution.

House robber

You're a robber. Houses along a street each contain some amount of money. You can't rob two adjacent houses (the alarm goes off). Maximize your take.

State: dp[i] = max money you can rob from houses 0..i.

Recurrence: at house i, you either rob it (take nums[i] + dp[i-2]) or skip it (take dp[i-1]). Whichever is bigger.

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        curr = max(prev1, nums[i] + prev2)
        prev2, prev1 = prev1, curr

    return prev1

Notice what's happening structurally. It's climbing stairs with a different recurrence. The 1D DP pattern is the same: define dp[i] in terms of a constant number of earlier entries, fill forward, collapse to O(1) space. Once you see that structure, a huge class of problems is the same problem with different numbers.

Family 2: Grid DP

Unique paths

An m × n grid. You start at the top-left, want to reach bottom-right, and can only move right or down. How many distinct paths?

State: dp[r][c] = number of ways to reach cell (r, c).

Recurrence: you arrived from above (r-1, c) or from the left (r, c-1). So dp[r][c] = dp[r-1][c] + dp[r][c-1].

Base cases: the entire top row and left column have exactly 1 path each (only one way to get there — go straight across or straight down).

def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]   # base: first row and column = 1

    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]

    return dp[m-1][n-1]

Time: O(m × n). Space: O(m × n). Can we do better on space?

Space optimize to O(n): each row only depends on the row above. Keep one 1D array and update it in place.

def unique_paths(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]   # row[c] was above; row[c-1] is left
    return row[-1]

Min path sum

Same grid, but each cell has a cost. Find the path (right or down only) with the minimum total cost.

The structure is identical — same state, same recurrence direction. Swap + for min:

def min_path_sum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = 0

    for r in range(m):
        new_dp = [float('inf')] * n
        for c in range(n):
            from_above = dp[c]
            from_left  = new_dp[c - 1] if c > 0 else float('inf')
            new_dp[c] = grid[r][c] + min(from_above, from_left)
        dp = new_dp

    return dp[-1]

Two grid problems with nearly the same code — just different operations in the recurrence. That's why DP patterns pay off. Learn the grid template once. Variations are parameter changes.

Family 3: Knapsack (a teaser)

The 0/1 Knapsack problem is the template for a whole family of problems: coin change, partition equal subset sum, word break, target sum. They look completely different on the surface. They're all knapsack problems underneath.

The setup: n items, each with a weight and a value. A bag with capacity W. Maximize the total value without exceeding capacity. Each item is either included (0/1 — not fractional, not repeated).

State: dp[i][w] = max value using items 0..i with capacity w.

Recurrence:

• Skip item i: dp[i-1][w]
• Take item i (only if weights[i] <= w): values[i] + dp[i-1][w - weights[i]]

Take the max of those two.

def knapsack(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    # dp[w] = best value achievable with remaining capacity w
    dp = [0] * (W + 1)

    for i in range(n):
        # Iterate capacity backwards to avoid using item i twice
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])

    return dp[W]

The backwards iteration on w is the subtle trick that collapses the 2D table to 1D for the 0/1 case — by the time you update dp[w], you haven't yet touched dp[w - weights[i]] in this item's pass, so it still reflects the previous item's state.

The full knapsack family — unbounded knapsack, coin change, partition, target sum — is covered in depth at knapsack patterns. The variations change what "taking an item" means and whether you can repeat. The framework stays the same.

How to recognize a DP problem on sight

Interviewers won't label their problems "this is DP." The tell is in the phrasing:

Phrase in the problem	Likely DP family
"How many ways to..."	Counting DP (paths, stairs, coin combos)
"Maximum/minimum ... subject to..."	Optimization DP (knapsack, path sum, robber)
"Can you reach / is it possible to..."	Decision DP (word break, subset sum)
"Longest subsequence / substring..."	Subsequence DP (LCS, LIS, edit distance)
"First / last K choices matter"	State carries recent history

The secondary check: draw a small recursion tree for your brute-force solution. Do you see any repeated subtrees? If yes, DP applies. If every leaf of the tree is unique, you might be looking at backtracking instead — which also uses recursion but doesn't have the overlap property, so caching doesn't help.

The worked derivation: coin change

Let's run the full four-step framework on a concrete problem that trips people up.

Problem: given coins of denominations [1, 5, 11] and an amount 13, what's the fewest coins to make exactly 13? (Coins can be reused.)

Step 1 — Brute-force recursion. To make amount a, try each coin. For coin c, you need 1 + min_coins(a - c) coins. Take the minimum across all valid coins.

def coin_change_brute(coins, amount):
    if amount == 0: return 0
    if amount < 0:  return float('inf')
    return 1 + min(coin_change_brute(coins, amount - c) for c in coins)

This is correct. It's also O(coin_count^amount) — exponential.

Step 2 — Identify overlapping subproblems. To make 13: try coin 1 → need 12. Try coin 5 → need 8. Try coin 11 → need 2. Computing min_coins(12) and min_coins(8) will both recurse into min_coins(7), which will both recurse into min_coins(6), and so on. Massive overlap.

Step 3 — Memoize.

def coin_change_memo(coins, amount):
    memo = {}
    def dp(a):
        if a == 0: return 0
        if a < 0:  return float('inf')
        if a in memo: return memo[a]
        memo[a] = 1 + min(dp(a - c) for c in coins)
        return memo[a]
    return dp(amount) if dp(amount) != float('inf') else -1

O(amount × len(coins)) time. O(amount) space.

Step 4 — Tabulate.

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0                             # base case: 0 coins to make amount 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], 1 + dp[a - c])

    return dp[amount] if dp[amount] != float('inf') else -1

For amount 13 with coins [1, 5, 11], dp[13] = 3 (11 + 1 + 1). Time: O(amount × coins). Space: O(amount) — can't reduce further because each cell depends on cells up to amount steps back.

Space: you can't collapse this one to O(1) because the recurrence looks at positions a - c for variable c. The O(amount) table is the finished solution.

Common mistakes that kill otherwise-good solutions

Wrong base cases. Half of all DP bugs live here. Draw out the first 3–4 cells of your table by hand before coding. If your base case is off by one, the error propagates through the entire table and you'll never find it by staring at the recurrence.

The wrong iteration order. 1D knapsack needs backward iteration; coin change needs forward. Get it backwards and you'll use the same item twice (or not at all). The rule: if you can reuse items, iterate forward. If each item is used at most once, iterate backward.

Confusing "number of ways" with "minimum ways." Problems that ask "how many paths" accumulate with +. Problems that ask "minimum cost" use min. They look almost identical in structure; mixing them up gives a wrong answer that passes some tests.

Skipping the recurrence, jumping to code. The recurrence relation is the DP. Write it out mathematically before writing a single line of code. dp[i] = max(dp[i-1], nums[i] + dp[i-2]) for house robber. Once that line is correct, the code writes itself.

Going directly to the optimized solution. It's tempting to skip straight to the O(1)-space version. Don't. Write the full n-dimensional table first, verify it gives the right answers, then optimize. Optimizing a broken solution is much harder than optimizing a working one.

When DP is the wrong tool

DP is not a cure-all. It needs overlapping subproblems — if your recursion tree has no duplicates, caching does nothing but waste memory.

Situations where DP is the wrong reach:

• Combinatorial search with no repeated subproblems → backtracking. Generating all permutations, N-Queens, Sudoku. Every state is unique by construction.
• Greedy suffices. If local optimal choices always lead to a global optimum (activity selection, fractional knapsack), greedy is O(n log n) and DP is overkill. You know greedy works when you can prove an exchange argument: swapping the greedy choice for any other never improves the answer.
• The constraint space is too large. If your DP state is (index, remaining_capacity) and capacity can be 10^9, a table is out of the question. You might need meet-in-the-middle, branch-and-bound, or an approximation.

If you're early in a topic and want the conceptual foundation before the patterns, the intro crash course builds this from scratch with simpler examples.

---

DP problems have a reputation for being impossible to solve in interviews without prior exposure. That reputation is partially deserved — if you're trying to memorize solutions, the search space is endless. But if you treat every problem as "write the recursion, find the overlap, cache it, tabulate it," you have a systematic process that works. The insight isn't in the answer. It's in the shape of the recursion tree.