Dynamic programming: 1D, 2D, knapsack, LIS and edit distance

What it is

Dynamic programming is a technique for problems where a solution decomposes into overlapping subproblems and the answer to a subproblem depends only on the subproblem, not on the path taken to reach it. You solve each subproblem once, store the result, and reuse it. That is the whole idea. Everything else is bookkeeping about what the subproblem is and what order to solve them in.

Two properties must hold. Optimal substructure: the optimal solution contains optimal solutions to its subproblems. Overlapping subproblems: the same subproblem is reached many times. Miss the first and DP gives wrong answers; miss the second and DP is just recursion with wasted memory.

Don't be confused: "DP" is not a class of problems, it is a property of your state definition. The same problem is exponential or polynomial depending on what you choose as the state. Backtracking over "which coins have I picked" has no overlap, because every path holds a different multiset. Rewrite the state as "how much target remains" and paths collapse onto each other, and the same problem becomes a polynomial DP. The state definition is the work; the recurrence usually writes itself once the state is right. If you cannot find the DP, you have the wrong state, not the wrong recurrence.

Don't be confused: memoisation and tabulation are the same algorithm. Top-down memoised recursion and bottom-up table filling compute the same values with the same complexity. They differ in three practical ways: top-down only computes the states it actually needs (which can be far fewer), bottom-up avoids recursion-depth limits and function-call overhead, and only bottom-up lets you drop the table to a rolling row for $O(1)$ or $O(n)$ space. Neither is "the real DP".

The problem it solves

Naive recursion for Fibonacci recomputes fib(30) millions of times. That is the toy version of a real problem: any recursive formulation whose call tree revisits states does exponential work for a polynomial amount of distinct information. DP converts the tree into a DAG and evaluates each node once.

More usefully, DP handles optimisation under constraints where greedy fails. coin_change in the code below is the standard demonstration: with coins ${1, 5, 6, 9}$ and a target of 11, greedy takes 9 first and needs $9+1+1 = 3$ coins, while the optimum is $5+6 = 2$. Greedy is correct for some coin systems (including most real currencies, which are designed to be canonical) and wrong for others, and you cannot tell by looking. DP does not care.

Mechanics

"""Dynamic programming: 1D, 2D, knapsack, LIS and edit distance.

Runnable: `python3 dynamic_programming.py`. The five shapes the interview
pattern list names, each with the state definition written out, because the
state definition IS the problem and the recurrence follows from it.
"""

import bisect
from functools import lru_cache


# --- 1D: the state is one index ----------------------------------------------
def house_robber(nums):
    """state: best[i] = the most you can take from the first i houses.
    recurrence: best[i] = max(skip house i, take house i + best[i-2])
    Rolling two variables instead of an array, because the recurrence only ever
    looks back two steps. O(n) time, O(1) space."""
    take, skip = 0, 0
    for n in nums:
        take, skip = skip + n, max(skip, take)
    return max(take, skip)


def coin_change(coins, amount):
    """state: fewest[a] = fewest coins summing exactly to a, or infinity.
    recurrence: fewest[a] = 1 + min(fewest[a - c] for each coin c <= a)

    UNBOUNDED knapsack: coins are reusable, so the inner loop runs FORWARD over
    amounts and each coin can be picked up again at a larger amount."""
    INF = float("inf")
    fewest = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and fewest[a - c] + 1 < fewest[a]:
                fewest[a] = fewest[a - c] + 1
    return -1 if fewest[amount] == INF else fewest[amount]


# --- 0/1 knapsack: the one where loop ORDER carries the meaning --------------
def knapsack_01(weights, values, capacity):
    """state: best[c] = best value achievable with capacity c, using the items
    considered so far.

    The inner loop runs BACKWARD over capacity. That single detail is what makes
    it 0/1 rather than unbounded: iterating downward means best[c - w] has not
    yet been updated for the current item, so it still refers to a solution
    WITHOUT this item. Iterate upward and you silently allow reuse.
    """
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):       # backward
            best[c] = max(best[c], best[c - w] + v)
    return best[capacity]


def knapsack_01_with_items(weights, values, capacity):
    """The 2D table version, kept because reconstructing WHICH items were chosen
    needs the full table. The 1D version above throws that history away."""
    n = len(weights)
    table = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            table[i][c] = table[i - 1][c]                    # skip item i
            if w <= c and table[i - 1][c - w] + v > table[i][c]:
                table[i][c] = table[i - 1][c - w] + v        # take item i
    chosen, c = [], capacity
    for i in range(n, 0, -1):
        if table[i][c] != table[i - 1][c]:                   # item i was taken
            chosen.append(i - 1)
            c -= weights[i - 1]
    return table[n][capacity], sorted(chosen)


# --- LIS: two algorithms, and the second is not a DP at all ------------------
def lis_quadratic(nums):
    """state: length[i] = length of the longest increasing subsequence ENDING at
    index i. The "ending at i" is what makes the recurrence work; "within the
    first i" does not, because it loses the information needed to extend."""
    if not nums:
        return 0, []
    length = [1] * len(nums)
    prev = [-1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i] and length[j] + 1 > length[i]:
                length[i], prev[i] = length[j] + 1, j
    best = max(range(len(nums)), key=lambda i: length[i])
    seq, k = [], best
    while k != -1:
        seq.append(nums[k])
        k = prev[k]
    return length[best], seq[::-1]


def lis_nlogn(nums):
    """O(n log n) via patience sorting. tails[k] is the SMALLEST possible tail
    of an increasing subsequence of length k+1. That array is sorted by
    construction, so binary search places each element.

    Note what this returns and does not: the LENGTH is correct, but `tails`
    itself is generally NOT a valid subsequence of the input. Reconstructing the
    actual sequence needs a parent array, as in the quadratic version.
    """
    tails = []
    for n in nums:
        i = bisect.bisect_left(tails, n)     # bisect_left: strictly increasing
        if i == len(tails):
            tails.append(n)
        else:
            tails[i] = n
    return len(tails), tails


# --- 2D: edit distance -------------------------------------------------------
def edit_distance(a, b):
    """state: d[i][j] = edits to turn a[:i] into b[:j].
    recurrence: if the last characters match, d[i][j] = d[i-1][j-1] (free).
    Otherwise 1 + min(delete a[i-1], insert b[j-1], substitute).

    The base row and column are not zeros: turning "" into b[:j] takes j
    insertions, so d[0][j] = j. Filling them with zeros is the most common bug.
    """
    m, n = len(a), len(b)
    d = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        d[i][0] = i
    for j in range(n + 1):
        d[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                d[i][j] = d[i - 1][j - 1]
            else:
                d[i][j] = 1 + min(d[i - 1][j],      # delete from a
                                  d[i][j - 1],      # insert into a
                                  d[i - 1][j - 1])  # substitute
    return d[m][n], d


def edit_ops(a, b, d):
    """Walk the table backwards to recover the actual edit script. Same idea as
    the knapsack reconstruction: the table holds the history, so read it."""
    ops, i, j = [], len(a), len(b)
    while i > 0 or j > 0:
        if i > 0 and j > 0 and a[i - 1] == b[j - 1] and d[i][j] == d[i - 1][j - 1]:
            i, j = i - 1, j - 1
        elif i > 0 and j > 0 and d[i][j] == d[i - 1][j - 1] + 1:
            ops.append(f"sub {a[i-1]}->{b[j-1]} at {i-1}")
            i, j = i - 1, j - 1
        elif i > 0 and d[i][j] == d[i - 1][j] + 1:
            ops.append(f"del {a[i-1]} at {i-1}")
            i -= 1
        else:
            ops.append(f"ins {b[j-1]} at {i}")
            j -= 1
    return ops[::-1]


# --- memoised recursion: the same DP, discovered rather than designed --------
def grid_paths(rows, cols, blocked=()):
    """Top-down is often the easier way to FIND the recurrence, because you write
    the question, not the fill order. Convert to bottom-up only if you need the
    space saving or Python's recursion limit is a problem."""
    blocked = set(blocked)

    @lru_cache(maxsize=None)
    def ways(r, c):
        if r >= rows or c >= cols or (r, c) in blocked:
            return 0
        if (r, c) == (rows - 1, cols - 1):
            return 1
        return ways(r + 1, c) + ways(r, c + 1)

    n = ways(0, 0)
    return n, ways.cache_info()


if __name__ == "__main__":
    houses = [2, 7, 9, 3, 1]
    # 7 and 9 are adjacent, so the greedy "take the two biggest" is illegal here.
    print("house_robber", houses, "->", house_robber(houses), "(2+9+1; 7+9 is adjacent)")
    print("coin_change([1,5,6,9], 11) ->", coin_change([1, 5, 6, 9], 11), "(5+6, greedy would say 9+1+1)")
    print("coin_change([2], 3)        ->", coin_change([2], 3), "(impossible)")

    print()
    w, v, cap = [3, 4, 5, 9], [4, 5, 6, 10], 12
    print("weights", w, "values", v, "capacity", cap)
    print("knapsack_01 (1D)      ->", knapsack_01(w, v, cap))
    total, items = knapsack_01_with_items(w, v, cap)
    print("knapsack_01 (2D)      ->", total, "using item indices", items,
          "weights", [w[i] for i in items])

    print()
    seq = [10, 9, 2, 5, 3, 7, 101, 18]
    n1, actual = lis_quadratic(seq)
    n2, tails = lis_nlogn(seq)
    print("sequence              :", seq)
    print("lis_quadratic         :", n1, actual)
    print("lis_nlogn             :", n2, "tails =", tails, "<- length is right, tails is not the subsequence")

    print()
    a, b = "intention", "execution"
    dist, table = edit_distance(a, b)
    print(f"edit_distance({a!r}, {b!r}) = {dist}")
    for op in edit_ops(a, b, table):
        print("   ", op)
    print("edit_distance('', 'abc') =", edit_distance("", "abc")[0])

    print()
    n, info = grid_paths(3, 4)
    print("grid_paths(3,4)       :", n, "paths;", info)
    n, info = grid_paths(3, 4, blocked=[(1, 1)])
    print("with (1,1) blocked    :", n, "paths;", info)

Five details, each of which is a question you will be asked.

The loop direction in knapsack_01 is the entire difference between 0/1 and unbounded. Both versions are the same three lines; one iterates capacity backward and one forward. Going backward, best[c - w] has not yet been touched for the current item, so it refers to a solution that does not include the item, which is what "use each item at most once" means. Going forward, best[c - w] may already include the current item, so the item gets reused, which is exactly the unbounded knapsack that coin_change wants. A one-character change to a range silently changes the problem being solved, and being able to say why out loud is one of the strongest signals available on this topic.

The base row and column of the edit distance table are not zeros. d[i][0] = i because turning a prefix of length $i$ into the empty string takes $i$ deletions, and d[0][j] = j symmetrically. Filling them with zeros is the most common edit-distance bug, and it produces answers that are too small in a way that looks plausible on short inputs.

lis_quadratic defines the state as "ending at index i", not "within the first i". This is the state-definition point made concrete. "Longest increasing subsequence within the first $i$ elements" is not enough information to extend, because you do not know what value the best subsequence ended on. "Ending at $i$" carries that, so the recurrence works, and the final answer is a max over all $i$ rather than the last cell. When a DP will not close, this is usually the fix: add to the state whatever the recurrence needs to know.

lis_nlogn is not a DP. It maintains tails[k], the smallest possible tail of any increasing subsequence of length $k+1$. That array is sorted by construction, so each new element is placed by binary search, giving $O(n \log n)$. It is the binary search pattern wearing a DP costume, and it is the standard follow-up once you produce the quadratic version.

grid_paths uses lru_cache and reports the cache statistics, which is the cheapest possible demonstration that memoisation is doing something. 17 misses and 6 hits on a 3 by 4 grid means 6 recursive calls returned without recomputing a subtree.

Worked example

house_robber [2, 7, 9, 3, 1] -> 12 (2+9+1; 7+9 is adjacent)
coin_change([1,5,6,9], 11) -> 2 (5+6, greedy would say 9+1+1)
coin_change([2], 3)        -> -1 (impossible)

weights [3, 4, 5, 9] values [4, 5, 6, 10] capacity 12
knapsack_01 (1D)      -> 15
knapsack_01 (2D)      -> 15 using item indices [0, 1, 2] weights [3, 4, 5]

sequence              : [10, 9, 2, 5, 3, 7, 101, 18]
lis_quadratic         : 4 [2, 5, 7, 101]
lis_nlogn             : 4 tails = [2, 3, 7, 18] <- length is right, tails is not the subsequence

edit_distance('intention', 'execution') = 5
    sub i->e at 0
    sub n->x at 1
    sub t->e at 2
    sub e->c at 3
    sub n->u at 4
edit_distance('', 'abc') = 3

grid_paths(3,4)       : 10 paths; CacheInfo(hits=6, misses=17, maxsize=None, currsize=17)
with (1,1) blocked    : 4 paths; CacheInfo(hits=4, misses=17, maxsize=None, currsize=17)

The LIS output is the most instructive line on this page. Both algorithms report length 4 and they agree, as they must. But the quadratic version returns the actual subsequence [2, 5, 7, 101], while tails from the fast version is [2, 3, 7, 18], which is not a subsequence of the input in that order at all: 3 appears before 5 in the input but after 2, and 18 appears after 101. The tails array is a set of best-possible endings, not a path. Candidates who return tails as "the LIS" are wrong and their answer looks right, because the length is right. If the problem asks for the sequence and not just its length, either use the quadratic version or add a parent array to the fast one, and say which you are doing.

Check the knapsack by hand. Weights [3,4,5,9], values [4,5,6,10], capacity 12. Items 0, 1 and 2 weigh exactly 12 and are worth $4+5+6 = 15$. The tempting alternative is item 3 (weight 9, value 10) plus item 0 (weight 3, value 4), also exactly 12, worth 14. So 15 is right and the greedy "best value per unit weight" heuristic would have picked item 0 first (ratio 1.33) and could plausibly land on the wrong answer. This is the input that shows the fractional-knapsack greedy does not carry over to 0/1.

grid_paths(3,4) is 10, which is $\binom{5}{2}$ as the closed form predicts, and blocking the single cell $(1,1)$ drops it to 4. The check: paths through $(1,1)$ number $\binom{2}{1} \times \binom{3}{1} = 2 \times 3 = 6$, and $10 - 6 = 4$. Having a closed form to check the DP against is a gift when it exists, and constructing one for the unobstructed case is a good way to validate an implementation before adding the obstacles that make the closed form impossible.

The edit script for intention to execution is five substitutions, which is worth inspecting because the textbook presentation of this exact pair usually shows a delete, three substitutions and an insert. Both are five operations, so both are optimal; the table has multiple optimal paths and the reconstruction picks whichever branch it tests first. If an interviewer's expected output differs from yours on a reconstruction problem, check whether both are optimal before assuming you are wrong.

Production evidence

Query planners use DP for join ordering. The System R optimiser introduced dynamic programming over subsets of relations: compute the best plan for every subset of tables, building up by size, because the best plan for a set of tables can be assembled from the best plans of its subsets. PostgreSQL still does this for queries below geqo_threshold (12 relations by default) and switches to a genetic algorithm above it, because the DP is $O(3^n)$ in the number of relations and stops being affordable. That threshold is a working example of a team choosing where exact DP stops paying.

The Viterbi algorithm is a DP over hidden state sequences, and it decodes convolutional codes in mobile and satellite communications, does part-of-speech tagging, and underpinned speech recognition for decades. The state is "most likely path ending in this state at this time", which is exactly the "ending at $i$" formulation used in lis_quadratic.

diff is an edit distance variant. Myers' algorithm, which is what Git uses by default, computes the shortest edit script between two sequences of lines. It is a refinement of the edit distance DP that searches the table diagonally and runs in $O(ND)$ where $D$ is the size of the edit script, which is fast in the common case where two file versions are mostly the same.

Sequence alignment in bioinformatics. Needleman-Wunsch (global alignment) and Smith-Waterman (local alignment) are the edit distance DP with a substitution scoring matrix and gap penalties instead of a flat cost of 1. Smith-Waterman is exact and is usually too slow for large database searches, which is why BLAST exists as a heuristic approximation. That pairing (exact DP, then a heuristic when the DP does not scale) is the same shape as the Postgres threshold above.

Levenshtein automata in Lucene. Lucene's fuzzy query builds an automaton accepting all strings within a given edit distance of the query and intersects it with the term dictionary's finite state transducer, rather than computing edit distance against every term. It is the trie-plus-pruning approach from the previous page, and it is the reason fuzzy search over millions of terms is affordable.

The debate

Top-down or bottom-up? Write top-down first. The reason is not preference: top-down lets you write the recurrence as a question, without deciding the fill order, and deciding the fill order is where people get stuck. @lru_cache on a clean recursive function is a correct DP in one line. Convert to bottom-up when you need the space reduction (the rolling array in house_robber and knapsack_01 is only possible bottom-up), when recursion depth is a real risk (Python defaults to 1,000 frames, and a 10,000-element 1D DP will hit it), or when the constant factor matters. State the conversion as a deliberate step, not as a correction.

Is the $O(n \log n)$ LIS worth writing in an interview? Only if asked, or if the stated constraints demand it. The quadratic version is six lines, obviously correct, and returns the actual subsequence; the fast version is four lines but is easy to get subtly wrong (bisect_left gives strictly increasing, bisect_right gives non-decreasing, and choosing wrong is a silent off by one) and does not give you the sequence. My position: write the quadratic version, state that an $O(n \log n)$ patience-sorting version exists and what its invariant is, and implement it if they want it. Volunteering the existence of the better algorithm gets most of the credit at a fraction of the risk.

When is DP the wrong tool? Three cases. First, when a greedy is provably correct, in which case DP is slower and more code, and the proof obligation is on you either way. Second, when the state space is too large: knapsack's $O(nW)$ is pseudo-polynomial, polynomial in the numeric value of $W$ rather than in the bits used to write it, so a capacity of $10^9$ makes the table impossible even with only 20 items. In that regime you want meet-in-the-middle, branch and bound, or an approximation scheme, and knowing that "pseudo-polynomial" is the reason is a real distinction. Third, when the problem lacks optimal substructure, in which case DP produces confident wrong answers, which is worse than being slow.

Follow-up Q&A

Is the knapsack DP polynomial or not? The complexity is $O(nW)$, which looks polynomial. It is pseudo-polynomial. The input size is $O(n \log W)$ bits, because $W$ is written in binary, so $O(nW)$ is exponential in the input length. 0/1 knapsack is NP-complete, and the DP does not contradict that. This is the crispest available test of whether a candidate understands complexity as a function of input size rather than of the numbers in the input, and it is asked often.

How do you reduce a 2D DP's space to $O(n)$? If the recurrence for row $i$ only reads row $i-1$, keep two rows and swap, or one row updated in the correct direction as knapsack_01 does. The cost is that you lose the ability to reconstruct the solution path, which is why knapsack_01_with_items keeps the full table. If you need both minimal space and the path, the technique is Hirschberg's divide-and-conquer, which computes the alignment in $O(\min(m,n))$ space at the cost of doubling the time. Naming Hirschberg here is a strong signal because most people know only the two extremes.

Why does the greedy fail for coin_change with [1,5,6,9] but work for real money? Because a coin system is canonical when greedy is optimal for every amount, and real currency denominations are deliberately designed that way. ${1,5,6,9}$ is not canonical: at 11, greedy takes 9 then needs two 1s for a total of 3, while $5+6$ is 2. There is a known test (Pearson's algorithm) for deciding whether a given coin system is canonical, and it runs in polynomial time. The interview-relevant point: you cannot tell by inspection, so do not assert greedy without a proof or a stated assumption.

Your edit_distance treats insert, delete and substitute as cost 1 each. What if they differ? Change the constants in the min, and the algorithm is otherwise unchanged. This generalises to a full substitution matrix, which is exactly Needleman-Wunsch. One subtlety worth knowing: if a substitution costs more than a delete plus an insert, the substitution branch is never chosen and the metric silently changes character. Also, the Damerau variant adds transposition as a fourth operation, which needs one more term reading d[i-2][j-2], and it matters for typo correction because adjacent-character transposition is one of the most common human typing errors.

When would you memoise on a tuple that includes something other than indices? Whenever the recurrence's answer depends on it. A common example is "at most $k$ transactions" stock problems, where the state is (day, transactions_left, holding). The discipline: write down every variable the recursive call reads, and that set is your state. If the state includes something you did not put in the cache key, the memoisation is wrong and returns stale answers, which is a bug that produces plausible numbers rather than a crash.

How do you approach a DP problem you have never seen, live? In this order. One, solve a tiny instance by hand. Two, write the brute-force recursion, however slow. Three, ask what the recursive call actually depends on, and make that the cache key. Four, add @lru_cache and check the answer is unchanged. Five, only if needed, convert to a table and reduce space. Narrating those five steps is itself the answer to "how do you think about DP", and it is more convincing than producing a memorised recurrence.

Common misconceptions

"Dynamic programming means filling a table." It means solving each subproblem once. The table is one implementation. Memoised recursion is DP; so is an iterative rolling variable.

"The state is always the index." It is whatever the recurrence reads. Multi-dimensional states are normal, and the reason a problem seems impossible is usually a missing dimension.

"If it has optimal substructure, greedy will work." Optimal substructure is necessary for both greedy and DP but sufficient for neither. Greedy additionally needs the greedy choice property: a locally optimal choice is part of some globally optimal solution. 0/1 knapsack has optimal substructure and fails the greedy choice property, which is precisely why it needs DP while fractional knapsack does not.

"$O(nW)$ for knapsack means it is efficient." Pseudo-polynomial, as above. The gap between the two is a genuine complexity-theory distinction and it has practical consequences.

"lru_cache makes any recursion fast." Only if states repeat. On a recursion whose arguments are never equal, it adds hashing overhead and unbounded memory growth and helps nothing. Also note maxsize=None never evicts, so on a large state space it is a memory leak in a long-running process.

Interview delivery note

Say the state definition as a full English sentence before you write anything: "Let best[c] be the maximum value achievable with capacity exactly c using the items I have considered so far." Then the recurrence, then the base case, then the fill order. Four sentences, thirty seconds, and they make the rest of the problem mechanical. Candidates who start writing loops before stating the state are the ones who get stuck, and interviewers can see it happening.

The senior-to-staff separator on DP is knowing where the DP stops being the right answer and saying so. A senior candidate produces a correct $O(nW)$ knapsack. A staff candidate produces the same code and then says, unprompted: "Note this is pseudo-polynomial. It is $O(nW)$ in the value of the capacity, so with 30 items and a capacity of a billion this table does not exist and I would go to meet-in-the-middle or branch and bound. The threshold is not theoretical: Postgres does exactly this, using DP join ordering under 12 relations and a genetic algorithm above it." That answer demonstrates the thing DP questions are actually probing, which is whether you understand the cost model well enough to know when to abandon your own solution.

The Staff & Team Lead Interview Reference