Dynamic Programming

1When DP applies

Dynamic programming is not a data structure. It is the decision to cache answers to subproblems once you have proved two things: optimal substructure (an optimal answer is built from optimal answers to smaller instances) and overlapping subproblems (the same smaller instance is asked more than once). Brute-force recursion already explores the tree; DP only pays when that tree revisits nodes.

Figure. Naive F(4) asks for F(2) on two different branches. Those two boxes are the same subproblem — that is the overlap DP caches.

The two tests

1. Optimal substructureAsk whether the best answer for n is assembled from best answers for strictly smaller inputs — not from some other kind of search.
2. Overlapping subproblemsDraw or imagine the recursion tree. If the same arguments appear on more than one branch, caching those answers changes exponential work into polynomial work.
3. If either failsNo overlap means memoization buys nothing (divide-and-conquer is enough). No optimal substructure means greedy or search may still work, but a DP table will encode the wrong claim.

2Memoization vs tabulation

Top-down memoization keeps the recursive shape and stores each result the first time it is computed. Bottom-up tabulation invents an order that fills a table from the base cases outward so every dependency is already present. Both avoid recomputation; they differ in control flow and in which states get evaluated when some states are unreachable.

Figure. Same recurrence: memo fills on demand from the root; tabulation fills a table in dependency order.

How each runs

1. Top-downCall the function on the full input. On a cache miss, recurse; on a hit, return the stored value. Only states that are actually asked are filled.
2. Bottom-upAllocate the table, write the base cases, then iterate in an order where each transition reads only already-written cells.
3. Same complexity classFor Fibonacci both are O(n) time. Memoization uses O(n) stack plus cache; tabulation can drop the stack, and a rolling pair of variables drops space to O(1).

Memoized Fibonacci

from functools import lru_cache

@lru_cache(None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

3State and transition

A DP solution is a state definition plus a transition. The state is the tuple of parameters that identify one subproblem — index in the array, remaining capacity, characters matched so far. The transition is the recurrence that builds a larger state's answer from smaller ones, together with the base cases that stop the recursion. Writing those three pieces explicitly before coding is the hard part; the loops are transcription.

Figure. Write three pieces before the loops: the state tuple that names one subproblem, the transition from strictly smaller states, and the base cells that need no recurrence.

Before you code

1. Name the stateAsk what you must know to answer a subproblem in isolation. Those parameters become the indices of the table (or the arguments of the memoized function).
2. Write the recurrenceExpress dp[state] using only strictly smaller states — take/skip, match/mismatch, last coin chosen — so evaluation cannot cycle.
3. Pin the base casesEmpty prefix, zero capacity, amount zero: the cells that need no recurrence. Wrong bases are the usual source of off-by-one interview bugs.

4Coin change (minimum coins)

Given coin denominations and a target amount, find the fewest coins that sum to that amount (unlimited supply of each coin). Let dp[a] be that minimum for amount a. The transition tries every coin c ≤ a and keeps dp[a−c] + 1. Unreachable amounts stay at a sentinel infinity so the final answer can report −1.

Figure. Final dp[a] for coins {1,2,5}: height is fewest coins. Amount 11 stands at 3; amount 8 needs three coins (no two-coin combination hits 8); amount 0 is the base at height 0.

How the table fills

1. Basedp[0] = 0 — zero amount needs zero coins. Every other cell starts at infinity.
2. TransitionFor each amount a from 1 to A, for each coin c with c ≤ a: dp[a] = min(dp[a], dp[a−c] + 1).
3. Read the answerdp[A] is the fewest coins, or −1 if it is still infinity. Time is O(n \times A) for n denominations.

Minimum coins, bottom-up

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    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

50/1 knapsack

Each item may be taken at most once. With n items and capacity W, dp[i][w] is the best total value using the first i items within capacity w. The transition is the max of skipping item i or taking it when weight[i] ≤ w: dp[i−1][w] versus value[i] + dp[i−1][w−weight[i]]. Time and space are O(nW) before the usual 1D compression.

Figure. At one cell the transition is max(skip, take). Here take wins 9 over skip 8 — each item still used at most once.

Take or skip

1. Skipdp[i][w] can always equal dp[i−1][w] — the best answer that ignores this item.
2. TakeIf weight[i] ≤ w, compare against value[i] + dp[i−1][w−weight[i]], which spends this item's weight in a subproblem that has not already used it.
3. Order matters for 1DCompressing to one array requires iterating capacity downward for 0/1 so a cell still holds the previous-item row when you read it. Ascending reuse is the unbounded (complete) knapsack.

0/1 knapsack, 1D compression

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):
            dp[w] = max(dp[w], val + dp[w - wt])
    return dp[W]

6Longest common subsequence

A subsequence keeps relative order but need not be contiguous. For strings X and Y of lengths m and n, dp[i][j] is the LCS length of the prefixes X[:i] and Y[:j]. Matching last characters gives 1 + dp[i−1][j−1]; a mismatch takes the max of dropping a character from either side. The whole table is O(mn) time and space.

Figure. dp table for X = ABC (rows) against Y = AC (columns), including the empty-prefix row and column of zeros. The bottom-right cell is 2.

Cell by cell

1. Basedp[0][*] = dp[*][0] = 0 — an empty prefix shares nothing.
2. Equal lettersIf X[i−1] = Y[j−1], set dp[i][j] = dp[i−1][j−1] + 1.
3. MismatchOtherwise dp[i][j] = max(dp[i−1][j], dp[i][j−1]).

LCS length

def lcs_length(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

7Edit distance

The Levenshtein distance is the fewest insertions, deletions and substitutions that turn string S into string T. With dp[i][j] as the distance between prefixes of lengths i and j, equal characters copy dp[i−1][j−1]; otherwise the cell is 1 plus the min of substitute, delete or insert — the three classical edits. Cost is again O(mn).

Same string×string cell lattice as Longest common subsequence, but each cell stores min insert / delete / substitute cost instead of a shared-subsequence length.

Three edits

1. SubstituteReplace S[i−1] with T[j−1]: cost 1 + dp[i−1][j−1].
2. DeleteDrop S[i−1]: cost 1 + dp[i−1][j].
3. InsertInsert T[j−1] into S: cost 1 + dp[i][j−1].

Levenshtein distance

def edit_distance(S, T):
    m, n = len(S), len(T)
    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 S[i - 1] == T[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],
                    dp[i - 1][j],
                    dp[i][j - 1],
                )
    return dp[m][n]

Coding lab. Edit distance cat to cut runs in the app, with checks on your output.

8Space optimisation and iteration direction

Many 2D tables depend only on the previous row (or previous two Fibonacci values). Keeping one row — or two rolling scalars — drops O(mn) or O(n) memory without changing the recurrence. The sharp interview trap is direction: 0/1 knapsack must scan capacity downward in the 1D array; unbounded knapsack and coin change scan upward so a coin can be reused.

Figure. When a cell needs only the previous row (or a suffix of it), drop the full table to rolling or 1D storage.

What you may drop

1. Row dependencyIf dp[i][j] reads only dp[i−1][*] (and maybe the current row to the left), store one row of length O(n) or two rows.
2. Rolling scalarsFibonacci only needs the previous two answers — O(1) space after the O(n) time pass.
3. Direction encodes reuseDescending capacity: each item once. Ascending capacity: an update can feed a later cell in the same pass, which is intentional reuse.