Classic DP Problems: Coin Change, Edit Distance and Knapsack

Most dynamic programming questions are variations on a small number of table shapes. Learn to recognise three of them, a one-dimensional table over an amount, a two-dimensional table over two sequences, and a two-dimensional table over items and a budget, and you can derive the rest as you go. This lesson solves one problem from each family with a deliberately fresh scenario.

Family one: a fare machine and the fewest coins

A fare-refund machine holds only 1, 5 and 6 unit coins, and must return a given amount using as few coins as possible. A greedy rule (always give the biggest coin that fits) sounds right, and it works for many real currencies. It does not work here: for 10 units it hands out a 6 and four 1s.

def fewest_coins(target, coins):
    """Fare machine refund: fewest coins that add up to target, or None."""
    INF = float("inf")
    fewest = [0] + [INF] * target
    last_coin = [0] * (target + 1)
    for amount in range(1, target + 1):
        for c in coins:
            if c <= amount and fewest[amount - c] + 1 < fewest[amount]:
                fewest[amount] = fewest[amount - c] + 1
                last_coin[amount] = c
    if fewest[target] == INF:
        return None
    used, a = [], target
    while a > 0:
        used.append(last_coin[a])
        a -= last_coin[a]
    return fewest[target], used

def greedy_coins(target, coins):
    used = []
    for c in sorted(coins, reverse=True):
        while target >= c:
            target -= c
            used.append(c)
    return len(used), used

coins = [1, 5, 6]
print("dp    :", fewest_coins(10, coins))
print("greedy:", greedy_coins(10, coins))
print("dp 7 with [4, 9]:", fewest_coins(7, [4, 9]))

dp    : (2, [5, 5])
greedy: (5, [6, 1, 1, 1, 1])
dp 7 with [4, 9]: None

The state is the amount remaining, and the recurrence is fewest[a] = 1 + min(fewest[a - c]) over every coin c that fits. The table has target + 1 cells and each does one step per coin, so the time is target x number of coins. The last line shows the infinity marker at work: with only 4 and 9 unit coins, 7 is impossible, and the function reports None instead of a bogus number. Greedy is correct only when the denominations have a special structure, which is exactly why you prove or test it rather than assume it.

Family two: comparing two sequences

A warehouse system receives parcel codes typed by hand, and wants to flag "PRACEL" as probably meaning "PARCEL". The standard measure is edit distance: the fewest insertions, deletions and substitutions that turn one string into the other. The table has one row per prefix of the first string and one column per prefix of the second; cell [i][j] is the distance between the first i characters and the first j.

def edit_distance(a, b):
    rows, cols = len(a) + 1, len(b) + 1
    d = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        d[i][0] = i                 # delete everything from a
    for j in range(cols):
        d[0][j] = j                 # insert everything from b
    for i in range(1, rows):
        for j in range(1, cols):
            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

a, b = "PARCEL", "PRACEL"
table = edit_distance(a, b)
print("    " + " ".join(f"{ch:>2}" for ch in "-" + b))
for ch, row in zip("-" + a, table):
    print(f"{ch:>2}  " + " ".join(f"{v:>2}" for v in row))
print("distance:", table[-1][-1])

     -  P  R  A  C  E  L
 -   0  1  2  3  4  5  6
 P   1  0  1  2  3  4  5
 A   2  1  1  1  2  3  4
 R   3  2  1  2  2  3  4
 C   4  3  2  2  2  3  4
 E   5  4  3  3  3  2  3
 L   6  5  4  4  4  3  2
distance: 2

The two swapped letters cost 2 because a transposition is not a primitive operation here: it is two substitutions. The first row and column are the base cases (turn nothing into a prefix, or a prefix into nothing). The related longest common subsequence problem uses the same grid but a different rule: on a match add 1 to the diagonal, otherwise take the larger of the cell above and the cell to the left. It works on any sequence, not only characters, so we can compare two delivery manifests.

def longest_common_subsequence(a, b):
    rows, cols = len(a) + 1, len(b) + 1
    L = [[0] * cols for _ in range(rows)]
    for i in range(1, rows):
        for j in range(1, cols):
            if a[i - 1] == b[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    # walk back to recover one actual subsequence
    i, j, out = len(a), len(b), []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i -= 1
            j -= 1
        elif L[i - 1][j] >= L[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return L[-1][-1], out[::-1]

monday = ["depot", "mill", "bridge", "harbour", "tower", "market", "depot"]
tuesday = ["depot", "bridge", "mill", "tower", "market", "school", "depot"]
print(longest_common_subsequence(monday, tuesday))

(5, ['depot', 'mill', 'tower', 'market', 'depot'])

A subsequence keeps order but may skip items, so the two routes share five stops in the same order. Note that more than one answer of length 5 exists (swapping mill for bridge also works); the walk-back picks one deterministically. If a question only needs the length, skip the walk-back entirely.

Family three: choose or skip under a budget

A cyclist is packing a cargo bike that can carry 10 kg. Each item has a weight and a value to the trip, and each item can be taken at most once. That is 0/1 knapsack. The table has one row per item considered so far and one column per capacity. For each cell you either leave the item (copy the cell above) or take it (value plus the best result with the leftover capacity from the row above), and keep the larger.

def best_cargo(items, capacity):
    """items: list of (name, weight_kg, value). Each item used at most once."""
    n = len(items)
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        name, w, v = items[i - 1]
        for cap in range(capacity + 1):
            best[i][cap] = best[i - 1][cap]                  # leave it
            if w <= cap:
                take = best[i - 1][cap - w] + v              # take it
                if take > best[i][cap]:
                    best[i][cap] = take
    chosen, cap = [], capacity
    for i in range(n, 0, -1):
        if best[i][cap] != best[i - 1][cap]:
            name, w, v = items[i - 1]
            chosen.append(name)
            cap -= w
    return best[n][capacity], chosen[::-1]

items = [("tent", 6, 30), ("stove", 4, 16), ("water", 5, 20),
         ("camera", 3, 14), ("books", 2, 6)]
print(best_cargo(items, 10))
print(best_cargo(items, 20))

(46, ['tent', 'stove'])
(86, ['tent', 'stove', 'water', 'camera', 'books'])

Recovering the choice works by comparing a cell with the one above it: if they differ, the item in that row was taken. With 10 kg the tent and stove win; with 20 kg everything fits. The time and space are both items x capacity. That is called pseudo-polynomial, because it depends on the numeric value of the capacity, not just on how many digits it takes to write down.

Common mistakes and the symptoms they cause

• Trusting greedy on coin change. It passes the tests with coins like 1, 5, 10, 25 and fails on 1, 5, 6: you get five coins where two suffice. Always try a small counter-example before using greedy.
• Not handling "impossible". Returning the sentinel (a huge number) as if it were an answer; the symptom is a result like inf or 1000000000 in your output. Check and return None or -1.
• Mixing up `i` in the table and `i-1` in the data. The table has an extra row for the empty prefix, so row i reads a[i-1]. Getting it wrong raises IndexError at the end or silently compares the wrong characters.
• Confusing subsequence with substring. A substring must be contiguous. If the question says contiguous, the recurrence resets to 0 on a mismatch instead of taking a max.

How this shows up in real projects and interviews

Edit distance and common-subsequence logic sit behind diff tools, spell suggestions and fuzzy search. Knapsack-style choice under a budget appears in ad allocation, test-suite selection under a time limit, and cargo or memory packing. Interview questions are rarely worded as the textbook problem. "Split an array into two groups of equal sum" is knapsack in disguise; "minimum deletions to make two strings equal" is LCS in disguise. When you see a new problem, ask which of the three table shapes it resembles, then write the state in a sentence before writing any code. For more problems that combine scanning with state, see Arrays and Strings.