Dynamic Programming

From recursion to memoization to tabulation — with the common DP shapes.

Dynamic programming (DP) is recursion plus memory. When a problem breaks into overlapping subproblems and the best answer is built from the best answers to smaller pieces (optimal substructure), you solve each subproblem once and reuse it. DP has a reputation for difficulty, but nearly every interview DP problem follows a handful of shapes.

When to use it

"Minimum / maximum cost / ways / length…"
"How many ways to…"
"Is it possible to…" with choices at each step
A brute-force recursion that recomputes the same arguments over and over

The four-step method

Define the state. What does dp[i] (or dp[i][j]) mean, in words? This is the crucial step.
Write the recurrence. How does a state depend on smaller states?
Set base cases.
Choose the order — top-down with memoization, or bottom-up filling a table.

Top-down vs bottom-up

from functools import cache

def climb_stairs(n):
    @cache
    def ways(i):
        if i <= 1:
            return 1
        return ways(i - 1) + ways(i - 2)
    return ways(n)

def climb_stairs(n):
    prev, cur = 1, 1
    for _ in range(n - 1):
        prev, cur = cur, prev + cur
    return cur

Top-down is often easier to derive in an interview — start there, then convert if asked about space.

Common shapes

Worked example: coin change

State: dp[a] = fewest coins that sum to a. Recurrence: dp[a] = 1 + min(dp[a - c] for c in coins if c <= a). Base: dp[0] = 0.

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

Worked example: edit distance (two sequences)

State: dp[i][j] = edits to turn a[:i] into b[:j].

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
    for j in range(n + 1): dp[0][j] = j
    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],      # delete
                                   dp[i][j - 1],      # insert
                                   dp[i - 1][j - 1])  # replace
    return dp[m][n]

[!INTERVIEW] Narrate the state definition Say the state in plain English before writing code: "dp of i is the fewest coins needed to make amount i." Interviewers grade the reasoning, and a clear state definition makes the recurrence almost write itself.

Pitfalls

A vague state definition — the most common reason DP solutions go wrong
Wrong loop order for 0/1 vs unbounded knapsack (iterate capacity backward for 0/1 when using a 1D array)
Forgetting the "impossible" case (infinity / −1)