Dynamic Programming Questions
Solving problems with overlapping subproblems and optimal substructure by memoization (top-down) and tabulation (bottom-up). Covers recognizing DP-amenable problems, defining state, transition and base cases, 1D and 2D sequence and grid formulations (knapsack and its variants, coin change, LIS, LCS, edit distance, sequence alignment, regular-expression and wildcard matching, counting-ways problems), interval DP (matrix chain, palindrome partitioning), space optimization with rolling arrays, solution reconstruction, longest paths in a DAG, game and expected-value DP, bitmask and tree DP, speeding up a DP (monotone queue, convex hull trick, divide-and-conquer optimization, bitsets, meet in the middle), and judging greedy versus DP. Ground covered elsewhere: probabilistic model inference, production caching and debugging practice, and general graph shortest-path algorithms.
Compute the nth Fibonacci number three ways: plain recursion, recursion with a cache, and an iterative bottom-up loop. For each, give the time and space complexity, and say roughly how many calls the plain version makes for n = 40. What goes wrong with each version when n is 100000 and the answer is wanted modulo 1e9+7?
Sample Answer
The idea
Fibonacci numbers are defined by F(0) = 0, F(1) = 1 and F(n) = F(n-1) + F(n-2). Written as plain recursion, the same smaller values are recomputed over and over, so the number of calls explodes. Two fixes remove the repetition: memoization (top-down: keep a cache of results keyed by the argument, so each n is computed once) and tabulation (bottom-up: fill a table from the smallest n upward). The loop version then notices that only the last two table cells are ever read and keeps just those.
The five things to state
- What one cell means.
table[i]is F(i). - The transition.
table[i] = table[i-1] + table[i-2], which is the definition itself. - Base cases.
table[0] = 0andtable[1] = 1. - Fill order. Ascending i, since each cell reads two smaller indices.
- Where the answer is.
table[n].
Counting the calls of the plain version
Let calls(n) be the number of calls, root included. Then calls(0) = calls(1) = 1 and calls(n) = 1 + calls(n-1) + calls(n-2). That solves to calls(n) = 2 * F(n+1) - 1, and the run below asserts that identity against real instrumented counts for n = 5, 10, 20 and 25. For n = 40 the recurrence gives F(41) = 165,580,141 and so 331,160,281 calls, about 3.3 x 10^8. The count is computed from the recurrence rather than by running the plain function at n = 40. The memoized version makes 2n - 1 calls (each n below the top does its real work once and its second visit returns at once), so 9, 19, 39 and 49 for the n values in the table.
The code
import random
import sys
from collections import Counter
sys.set_int_max_str_digits(100000) # str() of a 20,000-digit int is refused by default
MOD = 10**9 + 7
def fib_plain(n, counter):
counter[0] += 1
if n < 2:
return n
return fib_plain(n - 1, counter) + fib_plain(n - 2, counter)
def fib_memo(n, cache, counter):
counter[0] += 1
if n < 2:
return n
if n not in cache:
cache[n] = fib_memo(n - 1, cache, counter) + fib_memo(n - 2, cache, counter)
return cache[n]
def fib_table(n):
"""table[i] = F(i). Filled left to right; the answer is table[n]."""
table = [0] * (n + 1)
if n >= 1:
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table
def fib_loop_mod(n, mod=MOD):
a, b = 0, 1 # F(0), F(1)
for _ in range(n):
a, b = b, (a + b) % mod
return a
def fib_doubling_mod(n, mod=MOD):
"""Fast doubling: F(2k) = F(k)(2F(k+1) - F(k)), F(2k+1) = F(k)^2 + F(k+1)^2."""
def go(k):
if k == 0:
return 0, 1
a, b = go(k // 2)
c = a * ((2 * b - a) % mod) % mod
d = (a * a + b * b) % mod
return (d, (c + d) % mod) if k % 2 else (c, d)
return go(n)[0]
# call counts: plain calls(n) = 1 + calls(n-1) + calls(n-2), calls(0) = calls(1) = 1
calls_by_recurrence = [1, 1]
for n in range(2, 41):
calls_by_recurrence.append(1 + calls_by_recurrence[n - 1] + calls_by_recurrence[n - 2])
print("filled table for n=10:", fib_table(10))
print(" n F(n) plain_calls memo_calls")
for n in (5, 10, 20, 25):
c1, c2 = [0], [0]
value = fib_plain(n, c1)
assert value == fib_memo(n, {}, c2)
assert c1[0] == calls_by_recurrence[n] == 2 * fib_table(n + 1)[n + 1] - 1
print(f"{n:2d} {value:5d} {c1[0]:12d} {c2[0]:11d}")
print("n=40 plain calls (recurrence):", calls_by_recurrence[40])
cache_hits = 0
seen = set()
def permutations_with_cache(path, remaining):
global cache_hits
key = path
if key in seen:
cache_hits += 1
return
seen.add(key)
for x in remaining:
permutations_with_cache(path + (x,), remaining - {x})
permutations_with_cache((), frozenset(range(5)))
print("enumerating permutations of 5 items with a cache: states", len(seen), "hits", cache_hits)
print("path lengths among the 326 states:", dict(sorted(Counter(len(p) for p in seen).items())))
print("recursion limit:", sys.getrecursionlimit())
try:
fib_memo(5000, {}, [0])
except RecursionError:
print("memoized fib(5000) raised RecursionError")
print("bottom-up F(5000) has", len(str(fib_table(5000)[5000])), "digits")
print("F(100000) has", len(str(fib_table(100000)[100000])), "digits without a modulus")
print("F(100000) mod 1e9+7 by loop: ", fib_loop_mod(100000))
print("F(100000) mod 1e9+7 by doubling:", fib_doubling_mod(100000))
print("largest sum before reduction:", 2 * (MOD - 1), "fits in signed 32 bits:", 2 * (MOD - 1) <= 2**31 - 1)
# worked doubling step: from F(5) and F(6) get F(10) and F(11)
f5, f6 = fib_table(6)[5], fib_table(6)[6]
print(f"F(5)={f5}, F(6)={f6}: F(10)=F(5)*(2*F(6)-F(5))={f5 * (2 * f6 - f5)}, F(11)=F(5)^2+F(6)^2={f5 ** 2 + f6 ** 2}")
halvings, k = [100000], 100000
while k > 1:
k //= 2
halvings.append(k)
print("halvings from n=100000:", len(halvings) - 1, "->", halvings)
print("modulo: 17 % 5 =", 17 % 5, "; (7 + 8) % 5 =", (7 + 8) % 5, "; (7 % 5 + 8 % 5) % 5 =", (7 % 5 + 8 % 5) % 5)
random.seed(3)
for _ in range(300):
n = random.randint(0, 400)
assert fib_loop_mod(n) == fib_doubling_mod(n) == fib_table(n)[n] % MOD
print("300 random n in 0..400: loop, doubling and exact table agree mod 1e9+7")
Output:
filled table for n=10: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
n F(n) plain_calls memo_calls
5 5 15 9
10 55 177 19
20 6765 21891 39
25 75025 242785 49
n=40 plain calls (recurrence): 331160281
enumerating permutations of 5 items with a cache: states 326 hits 0
path lengths among the 326 states: {0: 1, 1: 5, 2: 20, 3: 60, 4: 120, 5: 120}
recursion limit: 1000
memoized fib(5000) raised RecursionError
bottom-up F(5000) has 1045 digits
F(100000) has 20899 digits without a modulus
F(100000) mod 1e9+7 by loop: 911435502
F(100000) mod 1e9+7 by doubling: 911435502
largest sum before reduction: 2000000012 fits in signed 32 bits: True
F(5)=5, F(6)=8: F(10)=F(5)*(2*F(6)-F(5))=55, F(11)=F(5)^2+F(6)^2=89
halvings from n=100000: 16 -> [100000, 50000, 25000, 12500, 6250, 3125, 1562, 781, 390, 195, 97, 48, 24, 12, 6, 3, 1]
modulo: 17 % 5 = 2 ; (7 + 8) % 5 = 0 ; (7 % 5 + 8 % 5) % 5 = 0
300 random n in 0..400: loop, doubling and exact table agree mod 1e9+7
What goes wrong at n = 100000 modulo 1e9+7
- Plain recursion never finishes: the call count has about as many digits as F(100000), which the run shows is 20,899 digits long. Time is exponential, so no machine finishes it.
- Memoized recursion does O(n) work but recurses n frames deep. CPython's default limit is 1000 frames (printed above), and the run shows
RecursionErroralready at n = 5000. Raising the limit trades the error for a risk of exhausting the stack, so the usual fix is to switch to the loop or to fill the cache from small n upward before asking for the big one. - Table or loop without a modulus keeps exact integers that reach 20,899 digits, so each addition costs time proportional to the digit count and the memory is large. Reducing modulo 1e9+7 after every addition keeps every stored value below 1e9+7.
- Reducing too late is the common slip: taking the modulus only on the final answer defeats the purpose in a fixed-width language, where the exact value overflows long before n = 100000. With the modulus applied at each step every stored value is at most 1,000,000,006, so the largest sum that can occur before a reduction is twice that, 2,000,000,012, which the run shows fits in a signed 32-bit integer.
Modulo means the remainder after division: 17 % 5 is 2. Reducing after every addition is safe because (7 + 8) % 5 and (7 % 5 + 8 % 5) % 5 are both 0, so the final remainder is the same whether or not the pieces were reduced on the way. A fixed-width language is one such as C or Java, where an integer has a set number of bits (32 for a signed int) and a value above 2,147,483,647 wraps around or is undefined instead of growing as Python's integers do.
Two checks sit in the same listing: the loop and the fast-doubling function give the same value for F(100000) mod 1e9+7 (911435502), and they agree with the exact table on 300 seeded values of n from 0 to 400.
When a cache does not help
A cache pays only when the same argument is requested more than once. Enumerating the orderings of 5 items by extending a path creates 326 distinct states and zero cache hits in the run, because every path is new. The states are the paths of every length: 1 empty path, 5 of length 1, 20 of length 2 (5 x 4), 60 of length 3, 120 of length 4 and 120 of length 5, which the line path lengths among the 326 states prints and which add up to 326. Two different calls never build the same path, because each call appends a different item to its own parent path, so a key is never requested twice. Fibonacci helps because its recursion tree has only n + 1 distinct arguments.
Fast doubling: how O(log n) arises
A typical interview expects the O(n) loop; fast doubling is the deeper follow-up when the interviewer asks for better. The identities come from squaring the matrix that advances Fibonacci by one step: Q^k = [[F(k+1), F(k)], [F(k), F(k-1)]], and Q^(2k) = (Q^k)^2. The top-left entry of the square is F(k+1)^2 + F(k)^2, which is F(2k+1). The top-right entry is F(k)(F(k+1) + F(k-1)), and since F(k-1) = F(k+1) - F(k) this equals F(k)(2F(k+1) - F(k)), which is F(2k). A worked step from the run: with F(5) = 5 and F(6) = 8, F(10) = 5 x (16 - 5) = 55 and F(11) = 25 + 64 = 89. So the pair (F(k), F(k+1)) yields the pair at 2k and 2k+1 with a few multiplications. go(k) calls itself on k // 2, so the argument halves each time: from n = 100000 the run lists 16 halvings down to 1. That is why both depth and work are about log2(n).
Complexity
| Version | States x work per state | Time | Space |
|---|---|---|---|
| Plain recursion | 2 * F(n+1) - 1 calls x O(1) | O(1.618^n) | O(n) call depth |
| Memoized | n + 1 states x O(1) | O(n) | O(n) cache plus O(n) call depth |
| Table | n + 1 cells x O(1) | O(n) | O(n) |
| Loop with two variables | n steps x O(1) | O(n) | O(1) |
| Fast doubling | about log2(n) levels x O(1) | O(log n) | O(log n) call depth |
The O(1) work per state assumes each addition is on small numbers, which is what the modulus guarantees.
Edge cases and common mistakes
- n = 0 must return 0 and n = 1 must return 1; the table code guards
n >= 1before writingtable[1]. - A cache created as a mutable default argument is shared between unrelated calls; the code passes a fresh
{}for each top-level call. - Off-by-one on call counts: the root call counts, which is why the counts above are 2F(n+1) - 1 and not 2F(n+1) - 2.
Running the code
python3.12 fibonacci.py
Standard library only. Save the listing as fibonacci.py and run the command above; it prints exactly the output shown.
Given two strings of length up to 2000, compute the length of their longest common subsequence. Define the table and recurrence, then explain how to cut memory from O(nm) to O(min(n,m)) and what that costs you.
Sample Answer
The idea
A subsequence keeps characters in their original order but may skip any of them ("ace" is a subsequence of "abcde"; "aec" is not). The longest common subsequence (LCS) of two strings is the longest sequence that is a subsequence of both. The insight: look only at the last character of each string. If they are equal, that character can be matched and the answer is 1 plus the LCS of the two shorter prefixes. If they differ, at least one of the two last characters is unused, so drop one or the other and take the better result.
The five things to state
- What one cell means.
dp[i][j]is the length of the LCS of the first i characters ofaand the first j characters ofb. - The transition. If
a[i-1] == b[j-1], thendp[i][j] = dp[i-1][j-1] + 1. Otherwisedp[i][j] = max(dp[i-1][j], dp[i][j-1]). When the last characters match, matching them is never worse than skipping one: there is always an optimal answer that uses both last characters, which is why the diagonal step is safe. The reason: take any common subsequence S of the two prefixes and look at where its last character is matched, at position p inaand q inb. If both p and q lie strictly before the final positions, the final matching characters can simply be added to S, making it longer, so S was not optimal. If p is the final position ofabut q is earlier, S's last character equalsa's last character, which equalsb's last character, so S can be re-pointed to matchb's final position instead of q, which is still after all of S's earlier matches inb; the length does not change. The case where q is final and p is earlier is the same, and if S is empty the single matching pair is a longer one. Small case:abagainstbb. The common subsequence "b" can match the b ofabto the first b ofbb, but re-pointing it to the last b gives the same length, anddp[2][2] = dp[1][1] + 1 = 1sinceaagainstbis 0 (both numbers are printed). When they differ, the last character ofaor the last character ofbis not in the common subsequence, and those are exactly the two options themaxcompares. - Base cases.
dp[0][j] = 0anddp[i][0] = 0: an empty prefix has nothing in common with anything. - Fill order. Row by row, left to right. Each cell reads the cell above, the cell to the left and the cell diagonally up-left, all of which are filled earlier.
- Where the answer is.
dp[n][m], the bottom-right cell, for strings of lengths n and m.
Brute force first
The recursion lcs_brute(i, j) implements the transition directly. For strings with no letter in common it makes 2 * C(n+m, n) - 1 calls (C is the binomial coefficient, "n+m choose n", the number of ways to pick n items out of n+m; C(4, 2) = 6, so n = m = 2 gives 2 * 6 - 1 = 11), counting the root call, because every call spawns two more until a prefix is empty. The memoized version (memoization means storing each result the first time it is computed so every (i, j) is worked out once) makes at most 1 + 2nm calls, since each of the n*m non-base states makes at most two calls. The run below checks both formulas at sizes 0, 1 and 2 and beyond: 1 call for n = 0, 3 for n = m = 1, 11 for n = m = 2, and 369,511 for n = m = 10 against 201 with the cache.
The recursive forms also hit Python's default recursion limit of 1000 frames: the depth is up to n + m, which is 4000 for two strings of length 2000. The table version has no recursion, so it is the one to use at that size; the last lines of the run show the memoized recursion raising RecursionError on the 2000 by 1500 pair.
The code
import random
from math import comb
calls = 0
def lcs_brute(a, b, i, j):
"""Length of the LCS of a[:i] and b[:j] by plain recursion."""
global calls
calls += 1
if i == 0 or j == 0:
return 0
if a[i - 1] == b[j - 1]:
return 1 + lcs_brute(a, b, i - 1, j - 1)
return max(lcs_brute(a, b, i - 1, j), lcs_brute(a, b, i, j - 1))
def lcs_memo(a, b):
"""Same recursion with a dict; returns (length, number of calls)."""
memo, count = {}, [0]
def go(i, j):
count[0] += 1
if i == 0 or j == 0:
return 0
if (i, j) not in memo:
if a[i - 1] == b[j - 1]:
memo[(i, j)] = 1 + go(i - 1, j - 1)
else:
memo[(i, j)] = max(go(i - 1, j), go(i, j - 1))
return memo[(i, j)]
return go(len(a), len(b)), count[0]
def lcs_table(a, b):
"""dp[i][j] = LCS length of a[:i] and b[:j]."""
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[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
def lcs_two_rows(a, b):
"""Keep only the previous row; the row length is min(len(a), len(b)) + 1."""
if len(b) > len(a):
a, b = b, a # LCS(a, b) == LCS(b, a)
prev = [0] * (len(b) + 1)
for i in range(1, len(a) + 1):
cur = [0] * (len(b) + 1)
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1] + 1
else:
cur[j] = max(prev[j], cur[j - 1])
prev = cur
return prev[-1]
def lcs_one_row(a, b):
"""One row: save the diagonal value before overwriting it."""
if len(b) > len(a):
a, b = b, a
row = [0] * (len(b) + 1)
for i in range(1, len(a) + 1):
diag = 0 # dp[i-1][0]
for j in range(1, len(b) + 1):
up = row[j] # dp[i-1][j], about to be overwritten
if a[i - 1] == b[j - 1]:
row[j] = diag + 1
else:
row[j] = max(up, row[j - 1])
diag = up
return row[-1]
def one_row_wrong_ascending(a, b):
"""Looks like the two-row code with the second row removed."""
row = [0] * (len(b) + 1)
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
row[j] = row[j - 1] + 1 # row[j-1] is already this row's value
else:
row[j] = max(row[j], row[j - 1])
return row[-1]
def one_row_wrong_descending(a, b):
"""Reversing j fixes the diagonal but breaks the left neighbour."""
row = [0] * (len(b) + 1)
for i in range(1, len(a) + 1):
for j in range(len(b), 0, -1):
if a[i - 1] == b[j - 1]:
row[j] = row[j - 1] + 1 # row[j-1] is still last row's: correct
else:
row[j] = max(row[j], row[j - 1]) # needs this row's left cell
return row[-1]
# 1. Brute-force call counts. Strings with no common letter are the worst case:
# calls(n, m) = 2 * C(n + m, n) - 1.
print("n m brute bound memo memo_bound")
for n, m in [(0, 0), (0, 3), (1, 1), (2, 2), (5, 5), (10, 10)]:
calls = 0
lcs_brute("a" * n, "b" * m, n, m)
_, memo_calls = lcs_memo("a" * n, "b" * m)
assert calls == 2 * comb(n + m, n) - 1 and memo_calls <= 1 + 2 * n * m
print(f"{n:<2} {m:<2} {calls:<6} {2 * comb(n + m, n) - 1:<6} "
f"{memo_calls:<5} {1 + 2 * n * m}")
# 2. The filled table for a small input.
a, b = "AGGTAB", "GXTXAYB"
dp = lcs_table(a, b)
print("\nTable for", a, "and", b)
print(" " + " ".join(["-"] + list(b)))
for i, row in enumerate(dp):
print(f"{'-' if i == 0 else a[i - 1]} " + " ".join(f"{v}" for v in row))
print("LCS length:", dp[-1][-1])
print("equal last characters, 'ab' vs 'bb':", lcs_table("ab", "bb")[-1][-1],
"| dropping the last 'b' of each leaves 'a' vs 'b':", lcs_table("a", "b")[-1][-1])
# 3. All versions agree with the brute force on seeded random small inputs.
rng = random.Random(7)
bad_asc = bad_desc = shown = 0
for _ in range(300):
x = "".join(rng.choice("abc") for _ in range(rng.randint(0, 8)))
y = "".join(rng.choice("abc") for _ in range(rng.randint(0, 8)))
calls = 0
want = lcs_brute(x, y, len(x), len(y))
assert want == lcs_memo(x, y)[0] == lcs_table(x, y)[-1][-1]
assert want == lcs_two_rows(x, y) == lcs_one_row(x, y)
asc, desc = one_row_wrong_ascending(x, y), one_row_wrong_descending(x, y)
bad_asc += asc != want
bad_desc += desc != want
if shown < 1 and asc != want and desc != want:
shown += 1
print(f"\nExample {x!r} vs {y!r}: correct {want}, "
f"ascending-wrong {asc}, descending-wrong {desc}")
print("300 random pairs: two-row and one-row match; "
f"wrong ascending: {bad_asc}, wrong descending: {bad_desc}")
# 4. Lengths 2000 and 1500: how many cells each version keeps.
rng = random.Random(2024)
s = "".join(rng.choice("ACGT") for _ in range(2000))
t = "".join(rng.choice("ACGT") for _ in range(1500))
full = lcs_table(s, t)
print("\nlen(s) =", len(s), "len(t) =", len(t))
print("full table cells:", len(full) * len(full[0]))
print("two-row cells: ", 2 * (min(len(s), len(t)) + 1))
print("LCS length:", full[-1][-1], lcs_two_rows(s, t), lcs_one_row(s, t))
try:
lcs_memo(s, t)
print("memoized recursion on the same pair: finished")
except RecursionError:
print("memoized recursion on the same pair: RecursionError (default limit 1000)")
print("empty string, either side:", lcs_table("", "abc")[-1][-1], lcs_table("abc", "")[-1][-1])
Output
n m brute bound memo memo_bound
0 0 1 1 1 1
0 3 1 1 1 1
1 1 3 3 3 3
2 2 11 11 9 9
5 5 503 503 51 51
10 10 369511 369511 201 201
Table for AGGTAB and GXTXAYB
- G X T X A Y B
- 0 0 0 0 0 0 0 0
A 0 0 0 0 0 1 1 1
G 0 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1
T 0 1 1 2 2 2 2 2
A 0 1 1 2 2 3 3 3
B 0 1 1 2 2 3 3 4
LCS length: 4
equal last characters, 'ab' vs 'bb': 1 | dropping the last 'b' of each leaves 'a' vs 'b': 0
Example 'abcaa' vs 'abcacaaa': correct 5, ascending-wrong 7, descending-wrong 3
300 random pairs: two-row and one-row match; wrong ascending: 117, wrong descending: 73
len(s) = 2000 len(t) = 1500
full table cells: 3003501
two-row cells: 3002
LCS length: 1109 1109 1109
memoized recursion on the same pair: RecursionError (default limit 1000)
empty string, either side: 0 0
Reading the filled table
In the table for AGGTAB and GXTXAYB, row T, column T holds 2: the best common subsequence of AGGT and GXT is GT. Row A, column A holds 3 (GTA), and the bottom-right cell holds 4 (GTAB). Every cell is either the diagonal value plus one (a match) or the larger of the neighbours above and to the left.
Cutting memory to O(min(n, m))
Row i of the table is computed only from row i-1 and the cells already filled in row i. So keep two rows, prev and cur, each with min(n, m) + 1 entries; the code swaps the strings first so the rows follow the shorter one (LCS is symmetric, so swapping is safe). Memory drops from (n+1)(m+1) cells to 2(min(n, m)+1): for the 2000 by 1500 pair that is 3,003,501 cells against 3,002.
Going one step further, a single row works if the diagonal value dp[i-1][j-1] is saved in a variable before the cell holding it is overwritten, as lcs_one_row does. The iteration order matters, and the run shows it. one_row_wrong_ascending fills left to right with no saved variable, so row[j-1] is already this row's value when the diagonal is needed; it over-counts (7 instead of 5 on abcaa against abcacaaa). one_row_wrong_descending fills right to left, which keeps the diagonal intact but now the left neighbour has not been computed yet, so it under-counts (3 instead of 5). On 300 seeded random pairs the first gets 117 wrong and the second 73, while lcs_two_rows and lcs_one_row match the brute force on all 300.
What it costs
- Time is unchanged. There are (n+1)(m+1) states and each does O(1) work, so time is O(nm) either way. Only space shrinks.
- The table is gone, so you get the length and nothing else. Walking back from the bottom-right cell to recover an actual subsequence needs the old rows. If the question also asks for the string, either keep the full table (O(nm) space) or use Hirschberg's divide-and-conquer, which finds the string in O(min(n, m)) extra space for roughly twice the time. Hirschberg's idea: cut
ain half; compute the LCS-length row of the first half againstbgoing forward and of the second half againstbgoing backward (each with the one-row trick); the position inbwhere the two rows add up to the largest total is where the optimal answer crosses the middle; then solve the two halves separately and join the results. A typical interview asks for the O(nm) table, then the length-only version in O(min(n, m)) memory, and only sometimes asks how to recover the string in small memory; Hirschberg's algorithm is deeper material that is rarely coded. - Slightly more delicate code. The saved-diagonal version is easy to get wrong, as the two broken versions show, so the two-row version is the safer default when memory is not tight.
Edge cases and common mistakes
- An empty string gives 0 with no special code, because the first row and column are already the base case.
- Mixing up subsequence and substring: a substring must be contiguous, and its table resets to 0 on a mismatch instead of taking the
max. - Initializing the table with
[[0] * m] * n, which makes every row the same list object. Build rows with a comprehension, aslcs_tabledoes. - Using
<or>=against the wrong index: with prefix lengths i and j, the characters being compared area[i-1]andb[j-1].
Running the code
Save the listing as lcs_length.py and run python lcs_length.py (Python 3.12, standard library only).
In your own words, what is dynamic programming and what two properties must a problem have for it to apply? Give one sequence or string example and one numeric optimization example, and say how you would spot them in a new problem.
Sample Answer
The idea
Dynamic programming (DP) is a way to solve a problem by writing the answer for a big input in terms of answers for smaller inputs, and then computing each smaller answer only once and reusing it. Plain recursion often recomputes the same small answers over and over; DP stores them so the work is done once per distinct subproblem instead of once per path that reaches it.
The two properties
- Optimal substructure. The best answer to the whole problem can be built from the best answers to smaller subproblems. Take coins of value 1, 3 and 4 and ask for the fewest coins that make 6. The best answer is one coin plus the best answer for a smaller amount: the best way to make 6 is a 3-coin plus the best way to make 3 (a single 3-coin), so 2 coins. Without this property, solving the pieces optimally does not give an optimal whole.
- Overlapping subproblems. The same smaller problem is needed many times by different branches of the recursion. Without this property there is nothing to reuse, and storing results costs memory for no gain (merge sort has the first property and not this one: its subproblems are disjoint halves).
Both are needed: substructure makes the recurrence correct, and overlap makes the table worth building.
A string example: can the text be split into words?
Given a string and a set of words, can the string be written as a concatenation of the words? State: ok[i] is True when the first i characters can be split into words. Transition: ok[i] is True when some word w ends exactly at position i and ok[i - len(w)] is True. Base case: ok[0] is True (the empty prefix). Order: i ascending, since each cell reads smaller indices. Answer: ok[len(s)]. The run prints the filled array for leetcode with the words leet and code: ok[4] and ok[8] are True.
A numeric optimization example: 0/1 knapsack
Items have a weight and a value; each is taken at most once; the total weight must stay within a capacity; maximize the total value. State: dp[i][c] is the best value using only the first i items with capacity c. Transition: dp[i][c] = max(dp[i-1][c], dp[i-1][c - w_i] + v_i) (leave item i, or take it if it fits). Base: row 0 is all zeros (no items, no value). Order: rows ascending, so row i reads row i-1. Answer: dp[n][capacity]. For weights 1, 3, 4, 5, values 1, 4, 5, 7 and capacity 7 the printed table ends at 9 (items of weight 3 and 4).
One cell by hand: the row item 3 (the first three items, with weight 4 and value 5 for item 3) at capacity 7 is 9. Leaving item 3 keeps the cell above, dp[2][7] = 5. Taking it spends 4 of the 7 units, leaving capacity 3, whose best with the first two items is dp[2][3] = 4, and adds its value 5, giving 4 + 5 = 9. The larger of 5 and 9 is 9.
How to spot a DP problem in a new question
- The question has the right shape. It asks for a count, a maximum or minimum, or a yes or no, over many ways of making a sequence of choices (a split, a take-or-skip, a path).
- The future depends on a small summary of the past. After some choices are made, what matters about them fits in a few numbers (position i, capacity left). That summary is the state.
- The brute force repeats itself. Write the plain recursion and count how many calls there are against how many distinct argument values it sees. For the word split on
arepeated n times followed byb, with wordsaandaa, the run prints 1 call at n = 0, 2 at n = 1, 4 at n = 2 and 28,656 calls at n = 20, against only 21 distinct positions. For the knapsack with n items of weight 1, calls are2^(n+1) - 1(1, 3, 7, 15 for n = 0 to 3 and 2,047 at n = 10) against 66 distinct(item, room)pairs at n = 10. A large gap between calls and distinct arguments is the overlap. - A greedy rule fails on a small example. With coins 1, 3 and 4 and a target of 6, taking the biggest coin first uses 3 coins (4 + 1 + 1), while the best is 2 (3 + 3). When a locally best choice can be wrong, the problem usually needs DP.
The code
import re
import random
from itertools import combinations
# ---------- Sequence example: can a string be split into dictionary words? ----------
word_calls = 0
seen_positions = set()
def can_split_brute(s, words, i=0):
"""Plain recursion on 'can s[i:] be split?'. No caching."""
global word_calls
word_calls += 1
seen_positions.add(i)
if i == len(s):
return True
ok = False
for w in words: # no early exit, so every branch is explored
if s.startswith(w, i) and can_split_brute(s, words, i + len(w)):
ok = True
return ok
def can_split_table(s, words):
"""ok[i] is True when the first i characters of s can be split into words."""
ok = [False] * (len(s) + 1)
ok[0] = True
for i in range(1, len(s) + 1):
# w ends at position i when s[0:i] ends with w; then the prefix before it must also split
ok[i] = any(ok[i - len(w)] for w in words if i >= len(w) and s.endswith(w, 0, i))
return ok
# ---------- Numeric optimization example: 0/1 knapsack ----------
knap_calls = 0
knap_states = set()
def knap_brute(weights, values, i=0, room=0):
"""Best value using items i.. with `room` capacity left. Take it or leave it."""
global knap_calls
knap_calls += 1
knap_states.add((i, room))
if i == len(weights):
return 0
best = knap_brute(weights, values, i + 1, room)
if weights[i] <= room:
best = max(best, values[i] + knap_brute(weights, values, i + 1, room - weights[i]))
return best
def knap_table(weights, values, capacity):
"""dp[i][c] = best value using only the first i items with capacity c."""
dp = [[0] * (capacity + 1) for _ in range(len(weights) + 1)]
for i in range(1, len(weights) + 1):
for c in range(capacity + 1):
dp[i][c] = dp[i - 1][c]
if weights[i - 1] <= c:
dp[i][c] = max(dp[i][c], dp[i - 1][c - weights[i - 1]] + values[i - 1])
return dp
def knap_reference(weights, values, capacity):
best = 0
for k in range(len(weights) + 1):
for pick in combinations(range(len(weights)), k):
if sum(weights[i] for i in pick) <= capacity:
best = max(best, sum(values[i] for i in pick))
return best
# ---------- A greedy rule that looks right and is not ----------
def coins_greedy(coins, target):
count = 0
for c in sorted(coins, reverse=True):
count += target // c
target %= c
return count if target == 0 else None
def coins_table(coins, target):
inf = float("inf")
best = [0] + [inf] * target
for t in range(1, target + 1):
for c in coins:
if c <= t and best[t - c] + 1 < best[t]:
best[t] = best[t - c] + 1
return best[target]
# 1. Overlapping subproblems, measured: calls versus distinct arguments.
print("word split, s = 'a' * n + 'b', words {a, aa}")
print("n calls distinct positions")
for n in [0, 1, 2, 10, 20]:
word_calls = 0
seen_positions.clear()
can_split_brute("a" * n + "b", ["a", "aa"])
print(f"{n:<3} {word_calls:<6} {len(seen_positions)}")
print("\nknapsack, n items of weight 1 and value 1, capacity 100, so every subset fits")
print("n calls bound 2^(n+1)-1 distinct (item, room)")
for n in [0, 1, 2, 3, 10]:
knap_calls = 0
knap_states.clear()
knap_brute([1] * n, [1] * n, 0, 100)
assert knap_calls <= 2 ** (n + 1) - 1
print(f"{n:<3} {knap_calls:<6} {2 ** (n + 1) - 1:<17} {len(knap_states)}")
# 2. Filled tables for small inputs.
s, words = "leetcode", ["leet", "code"]
ok = can_split_table(s, words)
print("\nsplit 'leetcode' with {leet, code}")
for i, flag in enumerate(ok):
print(f" ok[{i}] ({s[:i]!r}): {flag}")
w, v, cap = [1, 3, 4, 5], [1, 4, 5, 7], 7
dp = knap_table(w, v, cap)
print("\nknapsack weights", w, "values", v, "capacity", cap)
print("capacity: " + " ".join(str(c) for c in range(cap + 1)))
for i, row in enumerate(dp):
label = "no items" if i == 0 else f"item {i} "
print(f"{label:<9} " + " ".join(str(x) for x in row))
print("best value:", dp[-1][-1])
# 3. Both DPs agree with an independent reference on seeded random inputs.
rng = random.Random(4)
for _ in range(300):
words = rng.sample(["a", "ab", "b", "ba", "aab"], rng.randint(1, 4))
text = "".join(rng.choice("ab") for _ in range(rng.randint(0, 9)))
pattern = "(?:" + "|".join(words) + ")*" # regex "zero or more of these words", an independent reference
assert can_split_table(text, words)[-1] == bool(re.fullmatch(pattern, text))
word_calls = 0
assert can_split_brute(text, words) == can_split_table(text, words)[-1]
n = rng.randint(0, 7)
ws = [rng.randint(1, 6) for _ in range(n)]
vs = [rng.randint(0, 9) for _ in range(n)]
c = rng.randint(0, 12)
assert knap_table(ws, vs, c)[-1][-1] == knap_reference(ws, vs, c)
print("\n300 random word-split and 300 random knapsack cases match their references")
# 4. Greedy versus DP on coins.
print("\ncoins {1, 3, 4}, target 6: greedy", coins_greedy([1, 3, 4], 6),
"coins, DP", coins_table([1, 3, 4], 6), "coins")
Output
word split, s = 'a' * n + 'b', words {a, aa}
n calls distinct positions
0 1 1
1 2 2
2 4 3
10 232 11
20 28656 21
knapsack, n items of weight 1 and value 1, capacity 100, so every subset fits
n calls bound 2^(n+1)-1 distinct (item, room)
0 1 1 1
1 3 3 3
2 7 7 6
3 15 15 10
10 2047 2047 66
split 'leetcode' with {leet, code}
ok[0] (''): True
ok[1] ('l'): False
ok[2] ('le'): False
ok[3] ('lee'): False
ok[4] ('leet'): True
ok[5] ('leetc'): False
ok[6] ('leetco'): False
ok[7] ('leetcod'): False
ok[8] ('leetcode'): True
knapsack weights [1, 3, 4, 5] values [1, 4, 5, 7] capacity 7
capacity: 0 1 2 3 4 5 6 7
no items 0 0 0 0 0 0 0 0
item 1 0 1 1 1 1 1 1 1
item 2 0 1 1 4 5 5 5 5
item 3 0 1 1 4 5 6 6 9
item 4 0 1 1 4 5 7 8 9
best value: 9
300 random word-split and 300 random knapsack cases match their references
coins {1, 3, 4}, target 6: greedy 3 coins, DP 2 coins
Complexity
States times work per state. The word split has n + 1 states and each tries every word, so O(n * W * L) for W words of length up to L (the endswith comparison costs up to L). The knapsack has (n + 1)(capacity + 1) states at O(1) each, so O(n * capacity) time and the same space (reducible to O(capacity) by keeping a single row). That is pseudo-polynomial, meaning polynomial in the numeric value of the capacity rather than in the number of bits needed to write it.
Common mistakes
- Choosing a state that leaves out something the future needs (for the knapsack, forgetting the remaining capacity), so two different situations share one cell.
- Forgetting the base case for the empty prefix: nothing can then start a split, because every cell reads from an earlier cell that is itself unset.
- Reaching for DP when the problem has substructure but no overlap (divide and conquer), or when a proven greedy rule exists.
Running the code
Save the listing as dp_intro.py and run python dp_intro.py (Python 3.12, standard library only).
Explain the dynamic programming formulation of the 0/1 knapsack problem: what the state means, the transition, the base cases and the order you fill the table. Why does the recurrence give the optimal value, and why does the same idea not work as a greedy by value-per-weight?
Sample Answer
The idea
In 0/1 knapsack each item can be taken once or left, each has a weight and a value, and the total weight must stay within a capacity W; the goal is the largest total value. The insight is that the decision about the last item only changes how much capacity is left for the others, so the best answer for "first i items, capacity w" can be built from the best answers for "first i-1 items" with a smaller or equal capacity. "Dynamic programming" here means filling a table of such sub-answers so none is computed twice.
The five decisions of the DP
- What one cell means:
dp[i][w]is the maximum total value achievable using only the first i items and a capacity of w (total weight at most w). - Transition:
dp[i][w] = max(dp[i-1][w], value_i + dp[i-1][w - weight_i]), where the second option exists only whenweight_i <= w. The first option skips item i, the second takes it and spends its weight. - Base cases:
dp[0][w] = 0for every w (no items, no value). Capacity 0 gives 0 as well, because every weight in the example is positive. - Fill order: item index i from 1 to n; within a row, any order of w works, because row i reads only row i-1.
- Where the answer is read:
dp[n][W].
The brute force tries all 2^n subsets. Recursion that decides item by item makes 1, 3, 7, 15, 31, 63 calls (root counted) for n = 0 to 5 when every item fits, which is 2^(n+1) - 1, so it doubles with each item. The table has (n+1) x (W+1) cells, each filled with constant work.
Why the recurrence is optimal
A feasible subset is a set of items whose total weight is at most the capacity. The claim to prove is that dp[i][w] equals the best value over all feasible subsets of the first i items with capacity w. Induction is the standard way to prove a statement for every i: show it for the smallest case (i = 0, the base), then show that if it holds for i-1 items it also holds for i items (the step); the step can then be applied again and again, so the statement holds for every i.
- Base, i = 0: the only subset is the empty one, with value 0, which is what the table holds.
- Step: assume the claim for i-1 and every capacity. Take an optimal subset S for (i, w). If S leaves out item i, then S is a feasible subset of the first i-1 items with capacity w, so its value is at most
dp[i-1][w]. If S contains item i, then S without item i is a feasible subset of the first i-1 items with capacityw - weight_i, so its value is at mostdp[i-1][w - weight_i]and the value of S is at mostvalue_i + dp[i-1][w - weight_i]. So the optimum is at most the larger of the two formulas. Conversely, each formula is achieved by a real subset (by the hypothesis, plus item i in the second case), so the optimum is at least their maximum. Hence equality.
A small instance of the step, from the printed table: for the first two items (weights 1 and 3, values 1 and 4) and capacity 4, an optimal subset takes both items, value 5. It contains item 2, so removing item 2 leaves item 1 alone, a feasible subset of the first 1 item with capacity 4 - 3 = 1, worth at most dp[1][1] = 1; adding item 2 back gives 4 + 1 = 5, which is dp[2][4].
The step works because the choice for item i is independent of the choices for the earlier items except through the capacity left over. That property is called optimal substructure: an optimal solution contains optimal solutions to smaller versions of the same problem (here, the best subset of the first i-1 items for the capacity that remains).
Code
The driver prints the filled table from knapsack_table (never typed by hand), compares the answer with a try-every-subset reference, prints the recursion call counts, shows both greedy rules failing on a small instance, and then checks the DP against the reference on 300 seeded random instances.
import random
from itertools import combinations
def brute_subsets(items, cap):
"""Try every subset: the reference answer."""
best = 0
for k in range(len(items) + 1):
for subset in combinations(items, k):
if sum(w for w, _ in subset) <= cap:
best = max(best, sum(v for _, v in subset))
return best
def recursive(items, cap):
"""best(i, w): best value from items[i:] with w capacity left. Counts calls."""
calls = 0
def best(i, w):
nonlocal calls
calls += 1
if i == len(items):
return 0
weight, value = items[i]
skip = best(i + 1, w)
take = value + best(i + 1, w - weight) if weight <= w else 0
return max(skip, take)
return best(0, cap), calls
def knapsack_table(items, cap):
"""dp[i][w] = best value using only the first i items with capacity w."""
n = len(items)
dp = [[0] * (cap + 1) for _ in range(n + 1)] # row 0: no items, value 0
for i in range(1, n + 1):
weight, value = items[i - 1]
for w in range(cap + 1):
dp[i][w] = dp[i - 1][w] # skip item i
if weight <= w:
dp[i][w] = max(dp[i][w], value + dp[i - 1][w - weight]) # take item i
return dp
def greedy(items, cap, key):
total_w = total_v = 0
for w, v in sorted(items, key=key, reverse=True):
if total_w + w <= cap:
total_w += w
total_v += v
return total_v
items = [(1, 1), (3, 4), (4, 5), (5, 7)] # (weight, value)
cap = 7
dp = knapsack_table(items, cap)
print("items (weight, value):", items, " capacity:", cap)
print("dp[i][w] for w = 0.." + str(cap))
for i, row in enumerate(dp):
print(" i =", i, row)
print("answer dp[n][W]:", dp[-1][-1], " brute force:", brute_subsets(items, cap))
print("recursion calls when every item fits (root counted):")
for n in range(6):
sample = [(1, 1)] * n
print(" n =", n, "->", recursive(sample, 100)[1], "calls")
trap = [(10, 60), (20, 100), (30, 120)]
print("ratio greedy:", greedy(trap, 50, key=lambda it: it[1] / it[0]), " optimal:", knapsack_table(trap, 50)[-1][-1])
trap2 = [(6, 10), (5, 9), (5, 9)]
print("value greedy:", greedy(trap2, 10, key=lambda it: it[1]), " optimal:", knapsack_table(trap2, 10)[-1][-1])
random.seed(3)
wrong_ratio = 0
for _ in range(300):
n = random.randint(0, 8)
cap = random.randint(0, 20)
its = [(random.randint(1, 9), random.randint(1, 15)) for _ in range(n)]
want = brute_subsets(its, cap)
assert knapsack_table(its, cap)[-1][-1] == want == recursive(its, cap)[0]
wrong_ratio += greedy(its, cap, key=lambda it: it[1] / it[0]) < want
print("300 random instances: DP equals brute force; ratio greedy was below optimal on", wrong_ratio)
for big_w in (1000, 10**6):
print("W =", big_w, "takes", big_w.bit_length(), "bits; a table for 4 items has", 5 * (big_w + 1), "cells")
Output:
items (weight, value): [(1, 1), (3, 4), (4, 5), (5, 7)] capacity: 7
dp[i][w] for w = 0..7
i = 0 [0, 0, 0, 0, 0, 0, 0, 0]
i = 1 [0, 1, 1, 1, 1, 1, 1, 1]
i = 2 [0, 1, 1, 4, 5, 5, 5, 5]
i = 3 [0, 1, 1, 4, 5, 6, 6, 9]
i = 4 [0, 1, 1, 4, 5, 7, 8, 9]
answer dp[n][W]: 9 brute force: 9
recursion calls when every item fits (root counted):
n = 0 -> 1 calls
n = 1 -> 3 calls
n = 2 -> 7 calls
n = 3 -> 15 calls
n = 4 -> 31 calls
n = 5 -> 63 calls
ratio greedy: 160 optimal: 220
value greedy: 10 optimal: 18
300 random instances: DP equals brute force; ratio greedy was below optimal on 25
W = 1000 takes 10 bits; a table for 4 items has 5005 cells
W = 1000000 takes 20 bits; a table for 4 items has 5000005 cells
Reading the table
Items are (weight, value) = (1,1), (3,4), (4,5), (5,7) with W = 7. Take the cell dp[4][5]: skipping item 4 gives dp[3][5] = 6, taking it gives 7 + dp[3][0] = 7, so the cell is 7. For dp[4][7] skipping gives dp[3][7] = 9 and taking gives 7 + dp[3][2] = 8, so the answer is 9 (items of weight 3 and 4, values 4 and 5). Rows only ever read the row above, which is why the fill order inside a row does not matter.
Why value-per-weight greedy fails
Greedy sorts items by value divided by weight and takes each one that still fits. For the instance (10, 60), (20, 100), (30, 120) with W = 50 the ratios are 6, 5 and 4. Greedy takes the first two (weight 30, value 160), cannot fit the third (30 more would exceed 50), and stops at 160 while the optimum is 220 (the last two items). The unused 20 units of capacity are the loss: items cannot be split, so a high ratio does not guarantee that the capacity is used well. Picking by highest value fails too: with (6, 10), (5, 9), (5, 9) and W = 10 it takes the 10 and nothing else fits, giving 10, while the other two together give 18. On the 300 random instances in the driver, the ratio rule came out below the optimum on 25 of them, while the DP never did.
Greedy by ratio is exactly right for the fractional knapsack, where you may take part of an item, because then the leftover capacity can always be filled. The DP does not need that freedom: it compares the two real choices at every cell instead of committing to an order up front.
Complexity
Time O(nW): (n+1)(W+1) cells with O(1) work each. Space O(nW) for the full table. It is called pseudo-polynomial because W is a number whose value, not whose digit count, drives the cost; doubling the number of bits in W squares W itself, and the work is proportional to W. For example, W = 1000 takes 10 bits and W = 1,000,000 takes 20 bits; the second W is the square of the first, and the table for 4 items grows from 5,005 cells to 5,000,005, about 1,000 times as many (the last two printed lines).
Running the code
Save the listing as knap.py in the current directory, then run:
docker run --rm -v "$PWD":/w -w /w python:3.12 python knap.py
Python 3.12, standard library only.
Compute the minimum number of insertions, deletions and substitutions needed to turn one string into another (for example 'kitten' into 'sitting'). Define the state, base cases and recurrence, and give the time and space complexity, including how to reduce the space.
Sample Answer
The idea
Edit distance (also called Levenshtein distance) is the fewest single-character edits that turn one string into another, where an edit is an insertion, a deletion or a substitution. Look only at the last characters of the two strings. If they are equal, they cost nothing and the problem shrinks to the two shorter prefixes. If they differ, the last edit must be one of three things: delete the last character of the first string, insert the last character of the second, or replace one with the other. Take the cheapest of the three, plus one.
The five things to state
- What one cell means.
dp[i][j]is the fewest edits that turn the first i characters ofainto the first j characters ofb. - The transition. If
a[i-1] == b[j-1],dp[i][j] = dp[i-1][j-1]. Otherwisedp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), which are delete, insert and substitute in that order. Taking the diagonal on a match is safe, for this reason. Two neighbouring cells never differ by more than 1: from any set of edits for one cell you get a set for its neighbour by adding or removing one more insertion, deletion or substitution. Now suppose the last characters match. The delete option costsdp[i-1][j] + 1, anddp[i-1][j]is a neighbour ofdp[i-1][j-1], so it is at leastdp[i-1][j-1] - 1; the delete option is therefore at leastdp[i-1][j-1]. The insert option is bounded the same way. The diagonal option costs exactlydp[i-1][j-1], so no other move can beat the free match. The run checks the neighbour property on every cell of the 300 random tables. - Base cases.
dp[i][0] = i(delete all i characters) anddp[0][j] = j(insert all j characters). - Fill order. Row by row, left to right, so the cell above, the cell to the left and the diagonal are already filled.
- Where the answer is.
dp[len(a)][len(b)], the bottom-right cell.
Brute force first
edit_brute is the recurrence written as recursion. On strings with no letter in common it makes three calls per cell until a prefix is empty, so the call count follows its own recurrence: C(i, j) = 1 + C(i-1, j) + C(i, j-1) + C(i-1, j-1), with 1 on the edges. The first lines of the output check it, root call included: 1 call at n = m = 0, 4 at n = m = 1, 19 at n = m = 2, and 398,593 at n = m = 8. For kitten to sitting the brute force makes 3,032 calls (matches shrink the tree, but not enough), while a dict cache (memoization: remember each result the first time it is computed) makes 98 calls, at most 1 + 3nm, and the table loops compute 42 cells (6 x 7; the printed table has 7 x 8 = 56 entries, the other 14 being the base row and column).
The code
import random
from functools import lru_cache
calls = 0
def edit_brute(a, b, i, j):
"""Edit distance of a[:i] and b[:j] by plain recursion."""
global calls
calls += 1
if i == 0:
return j # insert the j remaining characters
if j == 0:
return i # delete the i remaining characters
if a[i - 1] == b[j - 1]:
return edit_brute(a, b, i - 1, j - 1)
return 1 + min(edit_brute(a, b, i - 1, j), # delete a[i-1]
edit_brute(a, b, i, j - 1), # insert b[j-1]
edit_brute(a, b, i - 1, j - 1)) # substitute
def edit_memo_calls(a, b):
"""Same recursion with a dict; returns (distance, number of calls)."""
memo, count = {}, [0]
def go(i, j):
count[0] += 1
if i == 0:
return j
if j == 0:
return i
if (i, j) not in memo:
if a[i - 1] == b[j - 1]:
memo[(i, j)] = go(i - 1, j - 1)
else:
memo[(i, j)] = 1 + min(go(i - 1, j), go(i, j - 1), go(i - 1, j - 1))
return memo[(i, j)]
return go(len(a), len(b)), count[0]
def edit_table(a, b):
"""dp[i][j] = fewest edits turning a[:i] into b[:j]."""
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a) + 1):
dp[i][0] = i
for j in range(len(b) + 1):
dp[0][j] = j
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 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
def edit_script(a, b, dp):
"""Walk back from the corner and list the edits, first to last."""
i, j, ops = len(a), len(b), []
while i > 0 or j > 0:
if i > 0 and j > 0 and a[i - 1] == b[j - 1] and dp[i][j] == dp[i - 1][j - 1]:
i, j = i - 1, j - 1
elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
ops.append(("replace", i - 1, a[i - 1], b[j - 1]))
i, j = i - 1, j - 1
elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
ops.append(("delete", i - 1, a[i - 1], None))
i -= 1
else:
ops.append(("insert", i, None, b[j - 1]))
j -= 1
return ops[::-1]
def apply_script(a, ops):
"""Apply edits right to left so earlier positions stay valid."""
s = list(a)
for kind, pos, _, new in reversed(ops):
if kind == "replace":
s[pos] = new
elif kind == "delete":
del s[pos]
else:
s.insert(pos, new)
return "".join(s)
def edit_two_rows(a, b):
"""Keep one previous row. Rows have min(len(a), len(b)) + 1 entries."""
if len(b) > len(a):
a, b = b, a # edit distance is symmetric
prev = list(range(len(b) + 1))
for i in range(1, len(a) + 1):
cur = [i] + [0] * len(b)
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[-1]
def edit_one_row(a, b):
"""One row, with the diagonal value saved before it is overwritten."""
if len(b) > len(a):
a, b = b, a
row = list(range(len(b) + 1))
for i in range(1, len(a) + 1):
diag, row[0] = row[0], i # diag = dp[i-1][0]
for j in range(1, len(b) + 1):
up = row[j] # dp[i-1][j]
if a[i - 1] == b[j - 1]:
row[j] = diag
else:
row[j] = 1 + min(up, row[j - 1], diag)
diag = up
return row[-1]
def wrong_ascending(a, b):
row = list(range(len(b) + 1))
for i in range(1, len(a) + 1):
row[0] = i
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
row[j] = row[j - 1] # row[j-1] is already this row's value
else:
row[j] = 1 + min(row[j], row[j - 1], row[j - 1]) # diagonal read from overwritten cell
return row[-1]
def wrong_descending(a, b):
row = list(range(len(b) + 1))
for i in range(1, len(a) + 1):
for j in range(len(b), 0, -1):
if a[i - 1] == b[j - 1]:
row[j] = row[j - 1] # still last row's value: correct
else:
row[j] = 1 + min(row[j], row[j - 1], row[j - 1]) # left not computed yet
row[0] = i
return row[-1]
band_cells = 0
def edit_bounded(a, b, k):
"""Exact distance if it is at most k, else None. Only cells with |i-j| <= k."""
global band_cells
n, m = len(a), len(b)
if abs(n - m) > k:
return None
if n == 0 or m == 0:
return max(n, m) # only inserts or only deletes
big = k + 1 # any value above k means "too far"
prev = [j if j <= k else big for j in range(m + 1)]
for i in range(1, n + 1):
cur = [big] * (m + 1)
if i <= k:
cur[0] = i
lo, hi = max(1, i - k), min(m, i + k)
for j in range(lo, hi + 1):
band_cells += 1
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = min(big, 1 + min(prev[j], cur[j - 1], prev[j - 1]))
if min(cur[lo:hi + 1]) > k:
return None # every path already costs more than k
prev = cur
return prev[m] if prev[m] <= k else None
def edit_auto(a, b):
"""Try k = 1, 2, 4, ... until the bounded version succeeds."""
k = 1
while True:
d = edit_bounded(a, b, k)
if d is not None:
return d, k
k *= 2
def weighted(a, b, ins=1, dele=1, sub=1):
"""Same table with a separate price for each operation."""
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
dp[i][0] = i * dele
for j in range(1, len(b) + 1):
dp[0][j] = j * ins
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
swap = 0 if a[i - 1] == b[j - 1] else sub
dp[i][j] = min(dp[i - 1][j] + dele, dp[i][j - 1] + ins, dp[i - 1][j - 1] + swap)
return dp[-1][-1]
def lcs_len(a, b):
"""Longest common subsequence length, used only to check the sub=2 identity."""
row = [0] * (len(b) + 1)
for ch in a:
diag = 0
for j in range(1, len(b) + 1):
up = row[j]
row[j] = diag + 1 if ch == b[j - 1] else max(up, row[j - 1])
diag = up
return row[-1]
def with_swaps(a, b):
"""Adds 'swap two neighbours' as one edit (the restricted, or OSA, version).
The swap option is part of the min inside the fill, so every later cell sees it."""
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a) + 1):
dp[i][0] = i
for j in range(len(b) + 1):
dp[0][j] = j
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
cost = 0 if a[i - 1] == b[j - 1] else 1
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
if i > 1 and j > 1 and a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]:
dp[i][j] = min(dp[i][j], dp[i - 2][j - 2] + 1)
return dp[-1][-1]
def swaps_memo(a, b):
"""Independent check: the same four-way recurrence written as a cached recursion."""
@lru_cache(maxsize=None)
def go(i, j):
if i == 0 or j == 0:
return i + j
best = min(go(i - 1, j) + 1, go(i, j - 1) + 1, go(i - 1, j - 1) + (a[i - 1] != b[j - 1]))
if i > 1 and j > 1 and a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]:
best = min(best, go(i - 2, j - 2) + 1)
return best
return go(len(a), len(b))
# 1. Call counts for strings with no letter in common (the worst case).
def predicted(n, m):
c = [[1] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
c[i][j] = 1 + c[i - 1][j] + c[i][j - 1] + c[i - 1][j - 1]
return c[n][m]
print("n m brute predicted memo memo_bound")
for n, m in [(0, 0), (0, 3), (1, 1), (2, 2), (5, 5), (8, 8)]:
calls = 0
edit_brute("a" * n, "b" * m, n, m)
_, memo_calls = edit_memo_calls("a" * n, "b" * m)
assert calls == predicted(n, m) and memo_calls <= 1 + 3 * n * m
print(f"{n:<2} {m:<2} {calls:<6} {predicted(n, m):<10} {memo_calls:<5} {1 + 3 * n * m}")
calls = 0
edit_brute("kitten", "sitting", 6, 7)
ks_table = edit_table("kitten", "sitting")
entries = len(ks_table) * len(ks_table[0])
computed = (len(ks_table) - 1) * (len(ks_table[0]) - 1)
print("kitten -> sitting brute calls:", calls,
"| memo calls:", edit_memo_calls("kitten", "sitting")[1],
f"| table entries: {entries}, computed by the loops: {computed} (the rest are the base row and column)")
# 2. The filled table and one optimal edit script.
a, b = "kitten", "sitting"
dp = edit_table(a, b)
print("\n " + " ".join(["-"] + list(b)))
for i, row in enumerate(dp):
print(f"{'-' if i == 0 else a[i - 1]} " + " ".join(str(v) for v in row))
ops = edit_script(a, b, dp)
print("distance:", dp[-1][-1], "| edits:", ops)
print("apply edits:", apply_script(a, ops))
# 3. Every version agrees with the brute force on seeded random inputs.
rng = random.Random(3)
bad_asc = bad_desc = shown = none_seen = pairs_checked = too_far = 0
for _ in range(300):
x = "".join(rng.choice("abc") for _ in range(rng.randint(0, 7)))
y = "".join(rng.choice("abc") for _ in range(rng.randint(0, 7)))
calls = 0
want = edit_brute(x, y, len(x), len(y))
table = edit_table(x, y)
assert want == edit_memo_calls(x, y)[0] == table[-1][-1]
assert want == edit_two_rows(x, y) == edit_one_row(x, y) == weighted(x, y)
assert weighted(x, y, 1, 1, 2) == len(x) + len(y) - 2 * lcs_len(x, y)
for i in range(len(table)):
for j in range(len(table[0])):
for di, dj in ((0, 1), (1, 0), (1, 1)):
if i + di < len(table) and j + dj < len(table[0]):
too_far += abs(table[i + di][j + dj] - table[i][j]) > 1
pairs_checked += 1
script = edit_script(x, y, table)
assert len(script) == want and apply_script(x, script) == y
for k in range(7):
got = edit_bounded(x, y, k)
assert got == (want if want <= k else None)
none_seen += got is None
assert edit_auto(x, y)[0] == want
asc, desc = wrong_ascending(x, y), wrong_descending(x, y)
bad_asc += asc != want
bad_desc += desc != want
if not shown and asc != want and desc != want:
shown = 1
print(f"\nExample {x!r} -> {y!r}: correct {want}, "
f"ascending-wrong {asc}, descending-wrong {desc}")
print("300 random pairs: all versions match; "
f"wrong ascending: {bad_asc}, wrong descending: {bad_desc}, "
f"bounded runs that returned None: {none_seen}")
print("neighbouring cells (right, below, diagonal) checked:", pairs_checked, "| pairs differing by more than 1:", too_far)
# 4. Banded version on two length-2000 strings that differ by a few edits.
rng = random.Random(99)
s = [rng.choice("ACGT") for _ in range(2000)]
t = s[:]
for pos in sorted(rng.sample(range(2000), 7), reverse=True):
kind = rng.choice(["sub", "ins", "del"])
if kind == "sub":
t[pos] = "T" if t[pos] != "T" else "A"
elif kind == "ins":
t.insert(pos, "G")
else:
del t[pos]
s, t = "".join(s), "".join(t)
exact = edit_one_row(s, t)
band_cells = 0
d, k = edit_auto(s, t)
print(f"\nlengths {len(s)} and {len(t)}: exact distance {exact}")
print(f"doubling search: distance {d} found with k = {k}, "
f"cells evaluated {band_cells} versus {len(s) * len(t)} for the full table")
assert d == exact
try:
edit_memo_calls("a" * 600, "b" * 600)
print("memoized recursion on two strings of length 600: finished")
except RecursionError:
print("memoized recursion on two strings of length 600: RecursionError (default limit 1000)")
# 5. Different prices and adjacent swaps.
print("\nsub cost 2 equals insert+delete only:", weighted("kitten", "sitting", 1, 1, 2),
"| len(a)+len(b)-2*LCS =",
len(a) + len(b) - 2 * lcs_len(a, b))
for p, q in (("ab", "ba"), ("abc", "bac")):
print(f"{p!r} -> {q!r}: plain", edit_table(p, q)[-1][-1], "| with swap", with_swaps(p, q))
rng = random.Random(5)
helped = 0
for _ in range(300):
x = "".join(rng.choice("abc") for _ in range(rng.randint(0, 7)))
y = "".join(rng.choice("abc") for _ in range(rng.randint(0, 7)))
assert with_swaps(x, y) == swaps_memo(x, y)
helped += with_swaps(x, y) < edit_table(x, y)[-1][-1]
print("300 random pairs: with_swaps matches the cached recursion; pairs where a swap lowered the distance:", helped)
Output
n m brute predicted memo memo_bound
0 0 1 1 1 1
0 3 1 1 1 1
1 1 4 4 4 4
2 2 19 19 13 13
5 5 2524 2524 76 76
8 8 398593 398593 193 193
kitten -> sitting brute calls: 3032 | memo calls: 98 | table entries: 56, computed by the loops: 42 (the rest are the base row and column)
- s i t t i n g
- 0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3
distance: 3 | edits: [('replace', 0, 'k', 's'), ('replace', 4, 'e', 'i'), ('insert', 6, None, 'g')]
apply edits: sitting
Example 'cbcb' -> 'cbcbcc': correct 2, ascending-wrong 5, descending-wrong 3
300 random pairs: all versions match; wrong ascending: 227, wrong descending: 58, bounded runs that returned None: 1060
neighbouring cells (right, below, diagonal) checked: 13935 | pairs differing by more than 1: 0
lengths 2000 and 1999: exact distance 7
doubling search: distance 7 found with k = 8, cells evaluated 54673 versus 3998000 for the full table
memoized recursion on two strings of length 600: RecursionError (default limit 1000)
sub cost 2 equals insert+delete only: 5 | len(a)+len(b)-2*LCS = 5
'ab' -> 'ba': plain 2 | with swap 1
'abc' -> 'bac': plain 2 | with swap 1
300 random pairs: with_swaps matches the cached recursion; pairs where a swap lowered the distance: 6
Reading the table
In the kitten to sitting table the bottom-right cell is 3: replace k with s, replace e with i, insert g. The diagonal 1, 1, 1, 1 carries the first replacement across the free matches of i, t and t. edit_script recovers the edits by walking back from the corner, checking at each cell which neighbour could have produced its value (a match going diagonally for free, otherwise a replace, a delete or an insert). The printed edits, applied by apply_script, rebuild sitting from kitten. The walk back needs the whole table, so it is the part that conflicts with the space reduction below.
Reducing the space
Row i depends only on row i-1 and on cells already filled in row i. edit_two_rows keeps just those two rows and edit_one_row keeps one, saving the diagonal value in a variable before overwriting it. Rows are sized by the shorter string (edit distance is symmetric, so swapping is safe), giving O(min(n, m)) memory.
Direction matters, and the run shows it. wrong_ascending fills left to right with no saved diagonal, so the "diagonal" it reads is the left neighbour that has just been rewritten; on cbcb to cbcbcc it returns 5 where the answer is 2, and over 300 seeded random pairs it is wrong 227 times. wrong_descending fills right to left, which keeps the diagonal intact but reads a left neighbour that has not been computed yet; it returns 3 on the same pair and is wrong 58 times. The saved-diagonal one-row version and the two-row version match the brute force on all 300.
Complexity
- Time: (n+1)(m+1) states, each O(1) (three lookups and a comparison), so O(nm).
- Space: table O(nm); two rows or one row O(min(n, m)). The memoized version also holds O(nm) dict entries and recurses to depth n + m, which can exceed Python's default limit of 1000 frames once the two lengths add up to about 1000, so tabulate for large inputs; the run shows the memoized version raising
RecursionErroron two strings of length 600. - Cost of the space saving: the length survives and the edit script does not. To keep both, run the same divide-and-conquer idea as Hirschberg's algorithm for LCS: split one string in half, compute the last row of the table for each half (one forward, one on the reversed halves), choose the split of the other string with the best total, and solve the two halves separately. That is still O(nm) time (roughly twice the table work) and linear extra space.
Bounded edit distance when only small distances matter
A typical interview asks for the table, the base cases, the complexity and the one- or two-row space reduction, and sometimes for the list of edits. The band, the doubling search, the different prices and the swap variant below are deeper material for follow-ups.
If the true distance d is small, an alignment can never stray far from the main diagonal: reaching cell (i, j) already costs at least |i - j| (the length gap has to be filled by inserts or deletes). So when you only care whether the distance is at most k, compute just the band of cells with |i - j| <= k and treat everything outside as "more than k". The strip of cells with |i - j| <= k is called the band, and restricting the table to it is the usual name for this idea (Ukkonen's band). edit_bounded does it: at most n * (2k + 1) cells, so O(kn) time, returns None when the distance exceeds k, and stops early if a whole row is above k. The check at 300 random pairs and k from 0 to 6 saw None 1,060 times and agreed with the full table every time.
When k is unknown, edit_auto tries k = 1, 2, 4, 8 and so on until one succeeds; the total work is a geometric series (each term is twice the one before, so the whole sum is less than twice the last term: the band widths 1, 2, 4, 8 add up to 15, under 2 x 8), still O(dn) where d is the true distance. On two strings of lengths 2000 and 1999 that differ by 7 edits it succeeded at k = 8 after evaluating 54,673 cells in all, against 3,998,000 for the full table. The rows in this code are still length m + 1, so memory stays O(m); a version that stores only the band would need O(k).
Other costs and transpositions
The same table handles unequal prices: replace the three + 1 terms with insert, delete and substitute costs (weighted). With a substitution cost of 2, a substitution is never better than a delete plus an insert, and the distance equals len(a) + len(b) - 2 * LCS (LCS is the longest common subsequence: the longest run of characters that appear in both strings in the same order, not necessarily next to each other), which the run checks (5 on kitten and sitting, and on every random pair). Counting an adjacent swap (ab to ba) as one edit adds one more transition, dp[i-2][j-2] + 1 when the last two characters of each string are swapped copies of each other. with_swaps does that inside the fill, so every later cell sees the cheaper value, and returns 1 for ab to ba and 1 for abc to bac, against 2 for plain edit distance in both cases. On 300 seeded random pairs it matches an independently written cached recursion of the same four-way rule (swaps_memo); a swap lowered the distance on 6 of those pairs. This version, the restricted (optimal string alignment) distance, does not allow editing a stretch of characters that has already been swapped. The full Damerau-Levenshtein distance does allow further edits between swapped characters, so the two can give different answers on some pairs.
Edge cases and common mistakes
- An empty string on either side: the base row or column gives the other string's length with no special code.
- Identical strings give 0; strings of different lengths give at least the length difference.
- Writing
min(...)without the+ 1on the mismatch branch, or adding 1 on a match. - Swapping which index belongs to which string (
a[i-1]pairs withdp[i],b[j-1]withdp[.][j]). - The algorithm does not depend on the language. In Java the rows would be
int[]and the loops would be the same, so the Python above carries over line by line.
Running the code
Save the listing as edit_distance.py and run python edit_distance.py (Python 3.12, standard library only).
Unlock Full Question Bank
Get access to all 10 Dynamic Programming interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.