Dynamic Programming You Can Actually Derive

Dynamic Programming Is Just Recursion With a Memory

Most people freeze on DP because they treat it as a bag of tricks to memorize. It isn't. DP is what you get when a recursive problem keeps solving the same subproblems, and you decide to stop redoing the work. That's the whole idea. If you can write the brute-force recursion, you're most of the way there.

DP applies when two things are true:

• Overlapping subproblems — the same inputs show up again and again in the recursion tree.
• Optimal substructure — the answer for a problem is built from answers to smaller versions of it.

Fibonacci is the toy example everyone shows, so here it is once, then never again. Naive fib(n) recomputes fib(3) an exponential number of times. Cache it and the tree collapses:

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

That @cache line is the entire lesson. You didn't invent an algorithm. You added a memory. Real DP problems are the same move on harder recurrences.

The Only Method You Need: Recurrence First

Do not start by drawing a table. Tables are the last step, and if you jump there first you'll flail. Follow this order every time:

1. Define the subproblem in words. "The most value I can carry using the first i items with w capacity left." Be precise. Vague definitions produce wrong recurrences.
2. Write the recurrence. How does the answer at one state depend on smaller states? Include the base cases.
3. Memoize the recursion. Verify it's correct on small inputs. This is your reference implementation.
4. Convert to bottom-up only if you need the speed or the space savings.

Step 4 is optional. A memoized recursion is real DP and often fast enough. Don't let anyone shame you into a table you can't derive.

Coin Change: Warm Up on the Recurrence

Given coin denominations and a target amount, find the fewest coins that sum to it. The subproblem: best(a) is the minimum coins to make amount a. To make a, you use some coin c, then you still owe a - c:

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount        # dp[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Read the loop against the recurrence: dp[a - c] + 1 is "solve the smaller amount, then add this coin." The base case dp[0] = 0 says making zero costs nothing. That's it. The table is just the recurrence evaluated in an order where every value you need is already computed.

Knapsack: Two Dimensions, Same Move

0/1 knapsack is where the "table" finally earns its name, because your state has two axes. You have items with weights and values and a capacity W. For each item you make one binary choice: take it or skip it.

Subproblem: dp[i][w] is the best value using the first i items with capacity w. The recurrence:

• Skip item i: dp[i-1][w]
• Take item i (only if it fits): dp[i-1][w - weight[i]] + value[i]

Take the max of the two.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]                      # skip
            if weights[i - 1] <= w:                      # take, if it fits
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1],
                )
    return dp[n][W]

Once you see it fill row by row, the classic space trick is obvious: each row only reads the row above, so you can collapse to a single 1D array. For 0/1 knapsack you iterate w downward so you don't reuse an item twice in the same pass. That direction detail is the kind of thing that separates "I memorized it" from "I derived it" — and it's exactly what an interviewer probes.

Edit Distance: When the State Is Two Strings

Edit distance (Levenshtein) asks the minimum single-character insertions, deletions, and substitutions to turn string a into string b. The state is a pair of prefix lengths: dp[i][j] is the cost to convert the first i chars of a into the first j chars of b.

Compare the last characters:

• If a[i-1] == b[j-1], they're free — carry over dp[i-1][j-1].
• Otherwise take the cheapest of insert (dp[i][j-1]), delete (dp[i-1][j]), or substitute (dp[i-1][j-1]), plus one.

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                     # delete all of a's prefix
    for j in range(n + 1):
        dp[0][j] = j                     # insert all of b's prefix
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

The base cases aren't decoration. Converting a string to empty means deleting every character, which is why row and column zero count up. Get those wrong and the whole table is garbage.

How to Spot and Attack DP in the Wild

Under interview pressure, look for these tells: the problem asks for a count of ways, a minimum/maximum, or a yes/no reachability, and each step you make a choice that shrinks the remaining problem. Sequences, grids, strings, and "reach a target amount" are DP magnets.

When you smell it, run the drill:

• Name the state so a stranger could implement it from your sentence.
• Write the recurrence and the base cases before any code.
• Memoize, test on a tiny input, then decide whether bottom-up is worth it.

The interview reps in /courses/dsa-python drill exactly this progression, and the same patterns extend naturally once you're comfortable in /courses/advanced-python-programming. Derive the recurrence and the table writes itself. Reach for a memorized table and you'll be stuck the moment the problem shifts by an inch.