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.
You have n items with weights and values (n up to 2000) and a knapsack of capacity W up to 100000. Return the maximum value you can carry and the indices of the items you chose. State the time and space complexity, and what happens to memory at those sizes.
Sample Answer
The idea
Pick a subset of n items (each used at most once) with total weight at most W and the largest total value, and also report which items you picked. Here n = 2000 and W = 100000. The value comes from a table over (items considered, capacity). The new difficulty at this size is memory and recovering the chosen items, not the recurrence.
The five decisions of the DP
- What one cell means:
dp[i][w]is the best total value from the first i items with capacity w. - Transition:
dp[i][w] = max(dp[i-1][w], value_i + dp[i-1][w - weight_i]), the second term only whenweight_i <= w. Either the last item is skipped, or it is taken and leavesw - weight_ifor the earlier ones; those two cases cover every subset. - Base cases:
dp[0][w] = 0for every w. - Fill order: items one by one; every cell of row i reads only row i-1.
- Where the answer is read:
dp[n][W]is the value. The items come from walking backwards: start at (n, W); if taking item i was strictly better there, record i and move to capacityw - weight_i; either way go to item i-1.
The brute force that decides items one at a time makes 1, 3, 7 and 15 calls (root counted) for n = 0 to 3 when every item fits, which is 2^(n+1) - 1, so it is hopeless for n = 2000. The table does (n+1)(W+1) = 200,102,001 cells of constant work, so time is O(nW).
The memory problem and the way out
The full table has 200,102,001 cells. As Python lists the 8-byte pointers alone come to 1.6 GB, before counting the integer objects they point at; even a compact 4-byte integer array would be about 800 MB. Three ways to cut it:
- Keep only one value row (O(W), under a megabyte of pointers). This gives the best value but loses the ability to walk back, because the earlier rows are gone.
- Keep the one value row plus one yes/no flag per (item, capacity): "taking this item at this capacity was strictly better". The walk-back needs only these flags. As one byte each that is n x (W+1) = 200 MB; packed as one bit each it is about 25 MB. The code below uses bytes.
- Divide and conquer on the item list (Hirschberg's idea) recomputes halves to rebuild the choices with O(W) memory, at roughly twice the running time. Concretely: split the items into a left half and a right half; compute the value row for the left half going forward and for the right half going backward, both keeping only one row; the best split of the capacity is the w that maximises
left[w] + right[W - w]; then repeat the same procedure on each half with its share of the capacity, until single items remain. Nothing but rows of length W is ever stored, and the recomputation costs about one more pass over the items. It is the choice when even the flags do not fit; a typical interview asks for the flag walk-back and mentions this as the way to go further, rather than asking for it to be coded.
The first listing below is saved as knapsack.py and the second as big.py; big.py imports knapsack from the first. The code uses the flag approach. Each item updates the whole row at once with built-in map calls instead of a Python loop, and the candidate row is built from the old row before anything is overwritten, so the same item cannot be counted twice. knapsack.py also contains the plain 2-D table so the small run can print the real filled table and compare against it.
How the three map lines work, for one item of weight wt and value val (the printed demo applies them to a 4-item instance):
old = dp[wt:]is the current best value for every capacity w fromwtup to W, before this item is considered ("skip the item").cand = list(map(add, dp[:cap + 1 - wt], repeat(val)))addsvalto each entry ofdp[:cap + 1 - wt]:mapwith two sequences callsaddon matching pairs, andrepeat(val)is an endless supply ofval. Entry k ofcandisdp[k] + val, which is the value of taking the item at capacityk + wt("take the item"). Both slices have the same length, socand[k]andold[k]describe the same capacity.flags[wt:] = bytes(map(gt, cand, old))compares them pair by pair (gtis the>operator);bytesturns True and False into 1 and 0. A 1 means taking the item is strictly better at that capacity.dp[wt:] = map(max, cand, old)keeps the larger of the two for each capacity.candis a finished list before this line runs, so the assignment reads old values only.
This is the same step as the loop for w in range(wt, cap + 1): cand = dp[w - wt] + val; ... that reads from the old row; the demo prints both and checks they agree.
import random
from itertools import combinations
from operator import gt
from itertools import repeat
from operator import add
def brute(weights, values, cap):
"""Reference: every subset (tiny inputs only)."""
best = 0
n = len(weights)
for k in range(n + 1):
for idx in combinations(range(n), k):
if sum(weights[i] for i in idx) <= cap:
best = max(best, sum(values[i] for i in idx))
return best
def recursive(weights, values, cap):
calls = 0
def best(i, w):
nonlocal calls
calls += 1
if i == len(weights):
return 0
skip = best(i + 1, w)
take = values[i] + best(i + 1, w - weights[i]) if weights[i] <= w else 0
return max(skip, take)
return best(0, cap), calls
def knapsack_table(weights, values, cap):
"""dp[i][w]: best value from the first i items with capacity w (full 2-D table)."""
n = len(weights)
dp = [[0] * (cap + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i - 1][w]
if weights[i - 1] <= w:
dp[i][w] = max(dp[i][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
return dp
def one_item_by_slices(dp, wt, val):
"""The three map lines of knapsack() for one item, returning every intermediate."""
cap = len(dp) - 1
old = dp[wt:]
cand = list(map(add, dp[:cap + 1 - wt], repeat(val)))
flags = bytes(map(gt, cand, old))
return old, cand, list(flags), dp[:wt] + list(map(max, cand, old))
def one_item_by_loop(dp, wt, val):
"""The same step as a plain loop; every read comes from the old row."""
new, flags = dp[:], []
for w in range(wt, len(dp)):
cand = dp[w - wt] + val
flags.append(1 if cand > dp[w] else 0)
new[w] = max(cand, dp[w])
return new, flags
def knapsack(weights, values, cap):
"""One value row plus one 'taken' byte per (item, capacity). Returns (best, indices)."""
dp = [0] * (cap + 1)
taken = []
for wt, val in zip(weights, values):
flags = bytearray(cap + 1)
if wt <= cap:
old = dp[wt:] # dp[w] for w >= wt, before this item
cand = list(map(add, dp[:cap + 1 - wt], repeat(val))) # dp[w - wt] + val
flags[wt:] = bytes(map(gt, cand, old)) # 1 where taking is strictly better
dp[wt:] = map(max, cand, old)
taken.append(flags)
chosen, w = [], cap
for i in range(len(weights) - 1, -1, -1): # walk the flags backwards
if taken[i][w]:
chosen.append(i)
w -= weights[i]
return dp[cap], sorted(chosen)
if __name__ == "__main__":
weights, values, cap = [1, 3, 4, 5], [1, 4, 5, 7], 7
table = knapsack_table(weights, values, cap)
print("weights", weights, "values", values, "capacity", cap)
for i, row in enumerate(table):
print(" i =", i, row)
print("table answer:", table[-1][-1], " fast version (best, chosen indices):", knapsack(weights, values, cap))
row_after_two_items = table[2]
old, cand, flags, new = one_item_by_slices(row_after_two_items, 4, 5)
print("item 3 (weight 4, value 5) applied to the row after item 2:", row_after_two_items)
print(" old = dp[4:] =", old)
print(" cand = dp[:4] + 5 =", cand)
print(" flags (cand > old) =", flags)
print(" new row =", new)
loop_new, loop_flags = one_item_by_loop(row_after_two_items, 4, 5)
print(" same step as a loop =", loop_new, loop_flags, " agrees:", loop_new == new and loop_flags == flags)
print("recursion calls, every item fits (root counted):")
for n in range(4):
print(" n =", n, "->", recursive([1] * n, [1] * n, 100)[1])
random.seed(11)
for _ in range(400):
n, cap = random.randint(0, 8), random.randint(0, 25)
ws = [random.randint(1, 10) for _ in range(n)]
vs = [random.randint(1, 20) for _ in range(n)]
best, idx = knapsack(ws, vs, cap)
assert best == brute(ws, vs, cap) == knapsack_table(ws, vs, cap)[-1][-1]
assert len(set(idx)) == len(idx) and sum(ws[i] for i in idx) <= cap and sum(vs[i] for i in idx) == best
print("400 random instances: value matches brute force and the chosen indices are feasible and add up to it")
Output:
weights [1, 3, 4, 5] values [1, 4, 5, 7] capacity 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]
table answer: 9 fast version (best, chosen indices): (9, [1, 2])
item 3 (weight 4, value 5) applied to the row after item 2: [0, 1, 1, 4, 5, 5, 5, 5]
old = dp[4:] = [5, 5, 5, 5]
cand = dp[:4] + 5 = [5, 6, 6, 9]
flags (cand > old) = [0, 1, 1, 1]
new row = [0, 1, 1, 4, 5, 6, 6, 9]
same step as a loop = [0, 1, 1, 4, 5, 6, 6, 9] [0, 1, 1, 1] agrees: True
recursion calls, every item fits (root counted):
n = 0 -> 1
n = 1 -> 3
n = 2 -> 7
n = 3 -> 15
400 random instances: value matches brute force and the chosen indices are feasible and add up to it
Reading the small run: the demo lines show the third item (weight 4, value 5) applied to the row [0, 1, 1, 4, 5, 5, 5, 5]. old is the tail from capacity 4, [5, 5, 5, 5]; cand is [0, 1, 1, 4] plus 5, which is [5, 6, 6, 9]; the flags [0, 1, 1, 1] say that taking the item only helps at capacities 5, 6 and 7 (at capacity 4 the two options tie at 5, and a tie keeps the item out); and the new row is the elementwise larger value, which is the i = 3 row of the table above. The walk-back starts at item index 3 with capacity 7. Taking it gives 7 + 1 = 8, which does not beat 9, so its flag is 0. Item index 2 was strictly better (9 against 5), so it is chosen and the capacity drops to 3; item index 1 was strictly better (4 against 1), so it is chosen and the capacity drops to 0. The chosen indices [1, 2] have weights 3 and 4 and values 4 and 5, total 9. The 400 seeded random instances check the value against try-every-subset and check that the returned indices are distinct, fit the capacity and add up to the value.
Now the full size, importing the function above:
import random, sys
sys.path.insert(0, ".")
from knapsack import knapsack # knapsack.py from the previous listing
n, cap = 2000, 100000
random.seed(5)
weights = [random.randint(1, 2000) for _ in range(n)]
values = [random.randint(1, 1000) for _ in range(n)]
row_bytes = sys.getsizeof([0] * (cap + 1))
print("cells in the full table:", (n + 1) * (cap + 1))
print("pointers alone, full table of Python lists (GB):", round((n + 1) * row_bytes / 1e9, 2))
print("one byte per cell flags (MB):", round(n * (cap + 1) / 1e6), " one bit per cell (MB):", round(n * (cap + 1) / 8 / 1e6))
best, chosen = knapsack(weights, values, cap)
print("best value:", best, " items chosen:", len(chosen), " weight used:", sum(weights[i] for i in chosen), " value check:", sum(values[i] for i in chosen))
Output:
cells in the full table: 200102001
pointers alone, full table of Python lists (GB): 1.6
one byte per cell flags (MB): 200 one bit per cell (MB): 25
best value: 266771 items chosen: 409 weight used: 99999 value check: 266771
The size lines are computed from n and W, so they are the same on every machine. The 409 chosen items weigh 99999, one under the capacity, and their values add up to the printed best, 266771.
Complexity
Time O(nW) = about 2.0 x 10^8 cell updates, here done inside built-in C loops. Space for the shipped code: O(W) for the value row plus O(nW) bytes for the flags (200 MB here), versus O(nW) machine words for the full table; one bit per flag brings it to n x W / 8. The result is called pseudo-polynomial because the cost grows with the value of W, not with the number of digits needed to write it.
Mistakes and edge cases
- An item heavier than W is skipped (
wt <= capguard) and its flag row stays all zero. - An empty item list or capacity 0 returns value 0 and no indices (covered by the random sizes starting at 0).
Running the code
Save the first listing as knapsack.py and the second as big.py in the same directory.
docker run --rm -v "$PWD":/w -w /w python:3.12 python knapsack.py
docker run --rm -v "$PWD":/w -w /w python:3.12 python big.py
Python 3.12, standard library only; the second command runs for tens of seconds.
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).
Return an actual longest common subsequence of two strings, not just its length. Fill the table, walk back through it to build the string, and say what you do when several answers tie.
Sample Answer
The idea
The length table already contains the decisions that produced every cell. To get the string, start at the bottom-right cell and walk back to the top-left, asking at each cell "how was this value produced?". A match means the character is part of the answer and you step diagonally. A non-match means the value was copied from the cell above or the cell to the left (whichever holds the larger value), so you step there and add nothing. Collect the matched characters on the way and reverse them at the end, because you meet them last-to-first.
The five things to state
- What one cell means.
dp[i][j]is the LCS length of the first i characters ofaand the first j characters ofb. - The transition. Equal last characters give
dp[i-1][j-1] + 1; otherwisemax(dp[i-1][j], dp[i][j-1]). - Base cases. Row 0 and column 0 are all 0 (an empty prefix matches nothing).
- Fill order. Row by row, left to right, so the three neighbours a cell reads are already filled.
- Where the answer is. The length is
dp[n][m]; the string is read by the walk back from that cell, which reads the cells in the reverse of the fill order.
Walking back
At cell (i, j) with i, j > 0:
- If
a[i-1] == b[j-1]: record that character and move to (i-1, j-1). Taking the match is safe because the cell's value came from the diagonal plus one. - Otherwise compare
dp[i-1][j](up) anddp[i][j-1](left). Move toward the larger one; that neighbour holds the same value as the current cell, so no length is lost. - Stop when i or j reaches 0.
The run below prints the table for ABCBDAB and BDCABA and the real path the code takes, one line per step.
When several answers tie
Often more than one string achieves the maximum length. For this input there are three: BCAB, BCBA and BDAB. The tie shows up in the walk as a cell where up == left (the first line of the trace, cell (7,6)). Both moves are valid and lead to different, equally long strings: sending ties up gives BCBA, sending ties left gives BDAB. So the right behaviour is to pick a fixed rule so the output is deterministic, and to say so. If the problem asks for a specific one, such as the lexicographically smallest (dictionary order), a walk back on the prefix table does not give it directly, because it builds the string from the end and cannot see which later characters will be chosen. Lexicographically smallest means the first in dictionary order: compare first characters, and on a tie compare the second, and so on, so BCAB comes before BDAB because C is before D at the second position.
A typical interview asks for the table, the walk back and a stated tie rule. The lexicographically smallest string, Hirschberg's method and the substring variant below are follow-ups and deeper material.
To build the smallest one, fill a second table over suffixes (suf[i][j] is the LCS of a[i:] and b[j:]) and build forward, one character at a time, in three moves:
- Say you still need
rcharacters (r = suf[i][j]). - Try the candidate characters in alphabetical order. For a candidate
c, find its first occurrence ina[i:]and inb[j:](the earliest match leaves the most room behind it). - Accept
cif the two strings after those occurrences still contain an LCS of lengthr - 1; otherwiseccannot start any longest answer from here, so try the next letter.
That is lcs_lex_smallest, and the run prints every step for ABCBDAB and BDCABA: with 4 characters needed, A is skipped because only 2 would remain after it, B is taken (3 remain, as required); with 3 needed, A and B are skipped, C is taken; then A, then B, giving BCAB. It equals the minimum of the brute-force set on all 300 random pairs.
The code
import random
from itertools import combinations
def build_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 walk_back(a, b, dp, prefer_up=True, trace=None):
"""Rebuild one LCS from the bottom-right cell. Ties go up or left by rule."""
i, j, picked = len(a), len(b), []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
if trace is not None:
trace.append(f"({i},{j}) match {a[i - 1]!r}, go diagonal")
picked.append(a[i - 1])
i, j = i - 1, j - 1
else:
up, left = dp[i - 1][j], dp[i][j - 1]
go_up = up > left or (up == left and prefer_up)
if trace is not None:
tie = " (tie)" if up == left else ""
trace.append(f"({i},{j}) up={up} left={left}{tie}, go {'up' if go_up else 'left'}")
if go_up:
i -= 1
else:
j -= 1
return "".join(reversed(picked))
def lcs_lex_smallest(a, b, trace=False):
"""Smallest LCS in dictionary order, using a table over suffixes."""
n, m = len(a), len(b)
suf = [[0] * (m + 1) for _ in range(n + 1)] # suf[i][j] = LCS of a[i:], b[j:]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
if a[i] == b[j]:
suf[i][j] = suf[i + 1][j + 1] + 1
else:
suf[i][j] = max(suf[i + 1][j], suf[i][j + 1])
i = j = 0
out = []
while suf[i][j] > 0:
for c in sorted(set(a[i:]) & set(b[j:])):
i2, j2 = a.index(c, i), b.index(c, j) # earliest match leaves most room
ok = suf[i2 + 1][j2 + 1] == suf[i][j] - 1
if trace:
print(f" need {suf[i][j]} more; try {c!r}: earliest at a[{i2}], b[{j2}], "
f"{suf[i2 + 1][j2 + 1]} left after it -> {'take' if ok else 'skip'}")
if ok:
out.append(c)
i, j = i2 + 1, j2 + 1
break
return "".join(out)
cells = 0
def last_row(a, b):
"""LCS(a, b[:j]) for every j, using two rows."""
global cells
prev = [0] * (len(b) + 1)
for ch in a:
cur = [0] * (len(b) + 1)
for j in range(1, len(b) + 1):
cells += 1
cur[j] = prev[j - 1] + 1 if ch == b[j - 1] else max(prev[j], cur[j - 1])
prev = cur
return prev
def hirschberg(a, b):
"""Actual LCS with only rows of length len(b)+1 alive at a time."""
if not a or not b:
return ""
if len(a) == 1:
return a if a in b else ""
mid = len(a) // 2
left = last_row(a[:mid], b)
right = last_row(a[mid:][::-1], b[::-1])
k = max(range(len(b) + 1), key=lambda k: left[k] + right[len(b) - k])
return hirschberg(a[:mid], b[:k]) + hirschberg(a[mid:], b[k:])
def longest_common_substring(a, b):
"""Contiguous version: a mismatch resets the cell to 0."""
best, end = 0, 0
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
if cur[j] > best:
best, end = cur[j], i
prev = cur
return a[end - best:end]
def all_lcs(a, b):
"""Reference: every longest common subsequence, by trying all subsequences of a."""
def is_subseq(s, t):
it = iter(t)
return all(ch in it for ch in s)
found, best = set(), 0
for k in range(len(a) + 1):
for idx in combinations(range(len(a)), k):
s = "".join(a[i] for i in idx)
if is_subseq(s, b):
if k > best:
best, found = k, set()
if k == best:
found.add(s)
return found
a, b = "ABCBDAB", "BDCABA"
dp = build_table(a, b)
print(" " + " ".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))
print("length:", dp[-1][-1])
trace = []
print("\nwalk back, ties go up:", walk_back(a, b, dp, True, trace))
print("\n".join(" " + line for line in trace))
print("walk back, ties go left:", walk_back(a, b, dp, False))
print("all LCS strings:", sorted(all_lcs(a, b)))
print("lexicographically smallest, step by step:")
print("lexicographically smallest:", lcs_lex_smallest(a, b, trace=True))
mid = len(a) // 2
left_row = last_row(a[:mid], b)
right_row = last_row(a[mid:][::-1], b[::-1])
sums = [left_row[k] + right_row[len(b) - k] for k in range(len(b) + 1)]
print("Hirschberg split of", a[:mid], "|", a[mid:], "against", b)
print(" left row (LCS of", a[:mid], "with b[:k]):", left_row)
print(" right row (LCS of", a[mid:], "with b[k:]):", [right_row[len(b) - k] for k in range(len(b) + 1)])
print(" sums:", sums, " best k:", sums.index(max(sums)), "-> halves", repr(b[:sums.index(max(sums))]), "and", repr(b[sums.index(max(sums)):]))
print("Hirschberg:", hirschberg(a, b))
print("longest common substring:", longest_common_substring(a, b),
"| LCS length:", dp[-1][-1])
# Check every method against the brute-force set on seeded random inputs.
rng = random.Random(11)
ties = 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)))
table, want = build_table(x, y), all_lcs(x, y)
n_best = table[-1][-1]
ties += len(want) > 1
for got in (walk_back(x, y, table, True), walk_back(x, y, table, False),
hirschberg(x, y)):
assert got in want and len(got) == n_best
assert lcs_lex_smallest(x, y) == min(want)
print("\n300 random pairs checked against all_lcs; pairs with more than one LCS:", ties)
# Hirschberg does about twice the table work (cell updates), with rows instead of the table.
rng = random.Random(5)
s = "".join(rng.choice("ACGT") for _ in range(200))
t = "".join(rng.choice("ACGT") for _ in range(200))
cells = 0
h = hirschberg(s, t)
print("n*m =", len(s) * len(t), "| Hirschberg cell updates =", cells,
"| length matches table:", len(h) == build_table(s, t)[-1][-1])
Output
- B D C A B A
- 0 0 0 0 0 0 0
A 0 0 0 0 1 1 1
B 0 1 1 1 1 2 2
C 0 1 1 2 2 2 2
B 0 1 1 2 2 3 3
D 0 1 2 2 2 3 3
A 0 1 2 2 3 3 4
B 0 1 2 2 3 4 4
length: 4
walk back, ties go up: BCBA
(7,6) up=4 left=4 (tie), go up
(6,6) match 'A', go diagonal
(5,5) up=3 left=2, go up
(4,5) match 'B', go diagonal
(3,4) up=1 left=2, go left
(3,3) match 'C', go diagonal
(2,2) up=0 left=1, go left
(2,1) match 'B', go diagonal
walk back, ties go left: BDAB
all LCS strings: ['BCAB', 'BCBA', 'BDAB']
lexicographically smallest, step by step:
need 4 more; try 'A': earliest at a[0], b[3], 2 left after it -> skip
need 4 more; try 'B': earliest at a[1], b[0], 3 left after it -> take
need 3 more; try 'A': earliest at a[5], b[3], 1 left after it -> skip
need 3 more; try 'B': earliest at a[3], b[4], 1 left after it -> skip
need 3 more; try 'C': earliest at a[2], b[2], 2 left after it -> take
need 2 more; try 'A': earliest at a[5], b[3], 1 left after it -> take
need 1 more; try 'B': earliest at a[6], b[4], 0 left after it -> take
lexicographically smallest: BCAB
Hirschberg split of ABC | BDAB against BDCABA
left row (LCS of ABC with b[:k]): [0, 1, 1, 2, 2, 2, 2]
right row (LCS of BDAB with b[k:]): [4, 3, 2, 2, 2, 1, 0]
sums: [4, 4, 3, 4, 4, 3, 2] best k: 0 -> halves '' and 'BDCABA'
Hirschberg: BDAB
longest common substring: AB | LCS length: 4
300 random pairs checked against all_lcs; pairs with more than one LCS: 65
n*m = 40000 | Hirschberg cell updates = 79719 | length matches table: True
LCS versus longest common substring
A substring must be contiguous; a subsequence may skip characters. The substring table has the same shape but a different rule: on a match, cur[j] = prev[j-1] + 1; on a mismatch the cell is 0 (the run is broken), and the answer is the largest cell anywhere, not the bottom-right one. For the same two strings the longest common substring has length 2 (AB and BD tie; the code returns the first it finds, AB), while the LCS has length 4. The substring is always a valid common subsequence, so its length is at most the LCS length.
Reconstruction without the full table
The table costs O(nm) memory. Hirschberg's method (hirschberg above) finds the actual string using only rows: split a in half, compute the last row of the LCS table for the first half against b, and the same for the reversed second half against reversed b. The split point k in b that maximizes left[k] + right[len(b) - k] is where an optimal alignment crosses the middle row, so the two halves are solved recursively on their own pieces. Worked on the example (the printed split lines): ABCBDAB is cut into ABC and BDAB. The left row holds the LCS of ABC with each prefix b[:k] of BDCABA, the right row the LCS of BDAB with each suffix b[k:], and the sums for k = 0 to 6 are 4, 4, 3, 4, 4, 3, 2. The largest sum, 4, is the LCS length, and it is reached at k = 0, 1, 3 and 4: each of those is a valid place for an optimal answer to cross the middle (k = 3 corresponds to BC from the left half and AB from the right half, which is the BCAB answer). The code takes the first maximum, k = 0, which hands the empty prefix to the left half and the whole of b to the right half, and the recursion returns BDAB. On the 200 by 200 input it does 79,719 cell updates against n*m = 40,000, about twice the table, because the first level costs about n*m and the work halves at each level below it (1 + 1/2 + 1/4 + ...). The recursion is about log2(n) deep. This listing is not memory-tight: every call keeps its two rows and its slices alive while it recurses, and the slices copy, so in the worst case it holds up to about m cells for each of about log2(n) levels. The textbook form of the method passes index ranges instead of slices and discards the rows before recursing, which needs only linear space.
Complexity
- Table plus walk back: time O(nm) to fill (nm states, O(1) each) and O(n + m) to walk back, since every step reduces i or j. Space O(nm) for the table.
- Hirschberg: time O(nm), about twice the table work as measured above; linear space in the textbook form, a little more in the listing for the reason given above.
Edge cases and common mistakes
- If either string is empty the loop never runs and the result is the empty string.
- Forgetting to reverse the collected characters, which yields the answer backwards.
- Walking back with the wrong index: with prefix lengths i and j the characters compared are
a[i-1]andb[j-1]. - Claiming the answer is unique. Unless the problem says "the" lexicographically smallest or "any", state which rule you used for ties.
- Trying to reconstruct from the two-row length-only version: the old rows are gone, so use the full table or Hirschberg.
Running the code
Save the listing as lcs_string.py and run python lcs_string.py (Python 3.12, standard library only).
In a tree whose node weights can be negative, find the maximum sum of weights along any path between two nodes (the path may be a single node). Describe what each node returns to its parent versus what it records as the global best, and give the complexity.
Sample Answer
The idea
Each node carries a number, its weight (it may be negative). A path here is any chain of connected nodes that never revisits a node, and its sum is the total of the weights on it. Its highest node (the one closest to the root) is the one place where it may bend, meaning turn from going up to going down: at that node it can use the left branch, the right branch, both, or neither. So the best path whose highest node is v is v's weight plus the best downward branch on each side, and the answer is the maximum of that quantity over all nodes v. The trap is that only one of the two branches can be extended upward past v, because a path that continues to v's parent can only arrive through one child. That is why each node reports one number to its parent and records a different number globally.
What each node returns versus records
For a node v with weight w:
- Meaning of the state:
down(v)is the largest sum of a path that starts at v and only goes downward (it always contains v). It is what v returns to its parent. - Transition:
left = max(0, down(v.left))andright = max(0, down(v.right)), thendown(v) = w + max(left, right). Themax(0, ...)drops a branch whose best sum is negative, because skipping a branch is allowed and is then at least as good. This is correct because any downward path from v is v followed by a downward path in exactly one child, or by nothing. - What v records globally:
through(v) = w + left + right, the best path that bends at v. The global best is the maximum ofthroughover all nodes. The parent cannot use this number: a path cannot go down one child, up through v and down the other child while also continuing to v's parent. - Base case: a missing child contributes 0, and the global best starts at negative infinity, not 0. A tree whose weights are all negative must answer with its largest single weight, so the empty path must not count.
- Fill order and answer: post-order (visit the left child, then the right child, then the node itself, because
down(v)needs both children's values). The answer is the global best after the root has been processed.
The brute force that follows the definition recomputes the two downward sums from scratch at every node, which re-walks everything below each node. An even blunter one tries every pair of nodes and sums the path between them. The second is the reference the random check below uses; the first is counted in the output.
Code
The driver prints the per-node trace, the call counts of the naive and one-pass versions on chains of 0 to 6 nodes (the root call and the calls on missing children are both counted), the edge cases, a comparison against the all-pairs reference on random trees, and what happens on a very deep chain.
import random
import sys
from collections import deque
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def build(level_order):
"""Build a tree from a level-order list; None marks a missing child."""
if not level_order or level_order[0] is None:
return None
root = Node(level_order[0])
queue, i = deque([root]), 1
while queue and i < len(level_order):
node = queue.popleft()
if i < len(level_order) and level_order[i] is not None:
node.left = Node(level_order[i])
queue.append(node.left)
i += 1
if i < len(level_order) and level_order[i] is not None:
node.right = Node(level_order[i])
queue.append(node.right)
i += 1
return root
def max_path_sum(root, trace=None):
"""Return (best path sum, number of calls). Empty tree -> (None, 1)."""
best = float("-inf")
calls = 0
def down(node):
# down(node) = best sum of a path that starts at node and only goes downward
nonlocal best, calls
calls += 1
if node is None:
return 0
left = max(0, down(node.left)) # a negative branch is never worth extending into
right = max(0, down(node.right))
through = node.val + left + right # path that bends at this node: recorded globally
best = max(best, through)
up = node.val + max(left, right) # path that continues to the parent: one side only
if trace is not None:
trace.append((node.val, left, right, through, up, best))
return up
down(root)
return (None if root is None else best), calls
def max_path_sum_naive(root):
"""Same answer, but every node recomputes its two downward sums from scratch."""
calls = 0
def down(node):
nonlocal calls
calls += 1
if node is None:
return 0
return node.val + max(0, down(node.left), down(node.right))
best = float("-inf")
stack = [root] if root else []
while stack:
node = stack.pop()
through = node.val + max(0, down(node.left)) + max(0, down(node.right))
best = max(best, through)
stack += [c for c in (node.left, node.right) if c]
return (None if root is None else best), calls
def max_path_sum_iterative(root, events=None):
"""Post-order with an explicit stack: no Python recursion limit.
Each node is pushed twice: first with seen=False (go and handle the children),
then with seen=True, which pops only after both children are finished."""
if root is None:
return None
best, up = float("-inf"), {}
stack = [(root, False)]
while stack:
node, seen = stack.pop()
if not seen:
stack.append((node, True))
stack += [(c, False) for c in (node.left, node.right) if c]
if events is not None:
events.append(f"pop {node.val} first time: push it again as 'seen', then its children")
continue
left = max(0, up[node.left]) if node.left else 0
right = max(0, up[node.right]) if node.right else 0
best = max(best, node.val + left + right)
up[node] = node.val + max(left, right)
if events is not None:
events.append(f"pop {node.val} second time: left={left} right={right} "
f"through={node.val + left + right} up={up[node]} best={best}")
return best
def max_path_sum_wrong_zero(root):
"""Common bug: best starts at 0, so an all-negative tree 'finds' an empty path."""
best = 0
def down(node):
nonlocal best
if node is None:
return 0
left, right = max(0, down(node.left)), max(0, down(node.right))
best = max(best, node.val + left + right)
return node.val + max(left, right)
down(root)
return best
def all_pairs_reference(root):
"""Brute force: try every pair of nodes, sum the nodes on the path between them."""
parent, depth, nodes = {root: None}, {root: 0}, []
stack = [root]
while stack:
node = stack.pop()
nodes.append(node)
for child in (node.left, node.right):
if child:
parent[child], depth[child] = node, depth[node] + 1
stack.append(child)
best = float("-inf")
for u in nodes:
for v in nodes:
a, b, total = u, v, 0
while a is not b: # climb the deeper one until they meet
if depth[a] >= depth[b]:
total += a.val
a = parent[a]
else:
total += b.val
b = parent[b]
best = max(best, total + a.val) # a is the lowest common ancestor
return best
# 1. Worked trace
tree = build([-10, 9, 20, None, None, 15, 7])
trace = []
print("answer, calls:", max_path_sum(tree, trace))
print("val left right through up best")
for row in trace:
print("%3d %5d %5d %7d %4d %6d" % row)
def count_nodes(node):
return 0 if node is None else 1 + count_nodes(node.left) + count_nodes(node.right)
def count_missing(node):
if node is None:
return 1
return count_missing(node.left) + count_missing(node.right)
real, gaps = count_nodes(tree), count_missing(tree)
print(f"calls on the example tree: {real} real nodes + {gaps} calls on missing children = {real + gaps}")
small = build([2, -1, 3])
events = []
print("iterative post-order on [2, -1, 3]:", max_path_sum_iterative(small, events))
print("\n".join(" " + e for e in events))
# 2. Calls on skewed trees: root counted, missing children counted
print("n naive_calls one_pass_calls")
for n in range(0, 7):
chain = None
for _ in range(n):
chain = Node(1, chain, None)
print(n, max_path_sum_naive(chain)[1], max_path_sum(chain)[1])
# 3. Edge cases
for name, t in [("single negative", build([-3])), ("two negatives", build([-2, -1])),
("empty", None), ("bend beats chain", build([2, -1, 3]))]:
print(name, "->", max_path_sum(t)[0])
print("all-negative with best=0 bug:", max_path_sum_wrong_zero(build([-3])), "(correct: -3)")
# 4. Random trees against the all-pairs reference
random.seed(11)
distinct = set()
for _ in range(400):
size = random.randint(1, 12)
values = [random.randint(-9, 9) if random.random() < 0.85 else None for _ in range(size)]
values[0] = random.randint(-9, 9)
t = build(values)
want = all_pairs_reference(t)
assert max_path_sum(t)[0] == max_path_sum_naive(t)[0] == max_path_sum_iterative(t) == want
distinct.add(tuple(values))
print("random trees checked:", len(distinct), "distinct level-order lists")
# 5. Deep trees: recursion limit versus the explicit stack
depth = 3000
chain = None
for _ in range(depth):
chain = Node(1, chain, None)
print("recursion limit:", sys.getrecursionlimit())
try:
max_path_sum(chain)
except RecursionError:
print("recursive version on a chain of", depth, "-> RecursionError")
print("iterative version on the same chain:", max_path_sum_iterative(chain))
Output:
answer, calls: (42, 11)
val left right through up best
9 0 0 9 9 9
15 0 0 15 15 15
7 0 0 7 7 15
20 15 7 42 35 42
-10 9 35 34 25 42
calls on the example tree: 5 real nodes + 6 calls on missing children = 11
iterative post-order on [2, -1, 3]: 5
pop 2 first time: push it again as 'seen', then its children
pop 3 first time: push it again as 'seen', then its children
pop 3 second time: left=0 right=0 through=3 up=3 best=3
pop -1 first time: push it again as 'seen', then its children
pop -1 second time: left=0 right=0 through=-1 up=-1 best=3
pop 2 second time: left=0 right=3 through=5 up=5 best=5
n naive_calls one_pass_calls
0 0 1
1 2 3
2 6 5
3 12 7
4 20 9
5 30 11
6 42 13
single negative -> -3
two negatives -> -1
empty -> None
bend beats chain -> 5
all-negative with best=0 bug: 0 (correct: -3)
random trees checked: 388 distinct level-order lists
recursion limit: 1000
recursive version on a chain of 3000 -> RecursionError
iterative version on the same chain: 3000
Reading the output
The trace columns are: val the node's weight; left and right the clipped downward sums from its children (0 when a child is missing or negative); through = val + left + right, the best path bending at this node; up = val + the larger of left and right, what the node returns to its parent; best the running global maximum after this node. The trace lists nodes in the order they finish (post-order). Node 20 has children 15 and 7, so it records through = 20 + 15 + 7 = 42, the best path overall, but returns only 20 + max(15, 7) = 35 to the root. The root -10 can bend over 9 and 35 for 34, which is less than 42, so the global best stays 42.
The tree is [-10, 9, 20, None, None, 15, 7] in level order, so only 5 nodes exist: -10 at the root, 9 and 20 below it, and 15 and 7 below 20. Each real node makes one call, and the code also calls down on every missing child: 9 has two, 15 has two and 7 has two, 6 in all. The run prints 5 + 6 = 11, which is the 11 in answer, calls.
On a chain of n nodes the one-pass version makes 2n + 1 calls (1, 3, 5, 7, ... in the table), one per node plus one per missing child. The naive version makes n(n + 1) calls on a chain (0, 2, 6, 12, 20, ...), which is quadratic.
The two-node case [-2, -1] answers -1 and the single node answers -3, which is why best starts at negative infinity. The best = 0 variant printed in the output returns 0 for the single node -3, a path with no nodes at all.
How the code is organised
max_path_sum defines the helper down inside it so that down can read and update two counters that belong to the outer function. Python needs the nonlocal best, calls line for that: without it, the assignments calls += 1 and best = max(best, through) make those names local to down, and the first one to run raises UnboundLocalError because the name is read before it has a value. The trace list is an optional argument that, when given, collects one row per node as it finishes, which is what the printed table shows.
The iterative version replaces the call stack with a list of (node, seen) pairs. Each node is pushed twice. The first pop (seen is False) pushes the node back as seen=True and then pushes its children on top of it, so the children are processed first. The second pop (seen is True) happens only after both children are finished, so their up values are ready. On [2, -1, 3] the run prints that sequence: node 2 first time, node 3 first time and second time, node -1 first and second time, and finally node 2 second time with left=0 right=3, giving through=5.
The all-pairs reference tries every pair (u, v) and sums the nodes on the path between them. It finds that path by climbing: whichever of the two nodes is deeper steps up to its parent, adding its weight, until both are the same node. That meeting node is their lowest common ancestor (the deepest node that has both u and v below it, possibly u or v itself), and its weight is added once at the end. This is slow (about n^2 pairs times a climb) but obviously correct, which is why it checks the fast code.
Complexity
Time: n states, constant work each (two max calls and an addition), so O(n). Space: the recursion depth is the tree height h (the number of nodes on the longest root-to-leaf chain), so O(h). A balanced tree is one where the two sides of every node have nearly equal height, so h is about log2(n); on a chain every node has one child, so h = n. CPython's default recursion limit is 1000 frames, and the output shows the recursive version raising RecursionError on a 3000-node chain. The iterative post-order version has no such limit; it keeps an explicit stack and a dictionary with one entry per node, so it uses O(n) memory.
Common mistakes
- Returning
through(v)to the parent. That lets a parent extend a path that has already bent, which builds a branching shape (a node with three neighbours on the chain) that is not a path, and it can overestimate the answer. - Not clipping negative branches with
max(0, ...), which forces a harmful subtree into the sum. - Starting the global best at 0 (shown above), which returns 0 for an all-negative tree. Starting it at
-1fails the same way whenever the true answer is below -1, as for the single node -3. - Forgetting that a path may be a single node, so a lone node is treated as invalid.
Running the code
Save the listing as tree_path.py (standard library only) and run:
docker run --rm -v "$PWD":/w -w /w python:3.12 python tree_path.py
A cashier always hands over the largest coin that fits. Give denominations and an amount where this gives a non-optimal answer, explain why, and describe the DP that fixes it.
Sample Answer
The idea
Greedy means "always take the locally best-looking choice and never reconsider". For coins, the cashier's rule takes the largest coin that still fits. It is only correct for some coin systems. With coins 1, 3 and 4 and an amount of 6, greedy takes 4, then has 2 left, and must use 1 + 1: three coins. The best answer is 3 + 3: two coins. Taking the 4 was a choice that cannot be undone, and it closed off the better combination.
Dynamic programming (DP) fixes this by not committing early. It solves every smaller amount first, remembers each answer, and builds larger amounts out of them, so every first coin is tried and the best is kept.
Why greedy fails and when it is safe
A coin system is called canonical when greedy is optimal for every amount. Greedy loses when the largest coin leaves a remainder that the smaller coins can only cover with many pieces, while a different combination hits the amount exactly: here taking the 4 leaves 2, which costs 1 + 1, so 4 + 1 + 1 = 6 uses three coins, while 3 + 3 = 6 uses two because two 3s fit 6 exactly and the 4 does not combine with the 3.
When greedy is safe:
- Coins that are powers of one base (1, 2, 4, 8, ... or 1, 5, 25, 125, ...) are canonical in the run below up to amount 500.
- The coins 1, 5, 10, 25 find no counterexample up to 200 in the run.
- A practical test for any system that contains a 1-coin: compare greedy with the DP for every amount below the sum of the two largest coins. The reason this is enough is a result attributed to Kozen and Zaks (1994, "Optimal bounds for the change-making problem"; the paper itself was not opened here): if greedy fails for some amount, the smallest failing amount is below the sum of the two largest coins.
is_canonicalin the code does exactly this check, and the run tests that attributed bound on 1298 random systems that do have a counterexample (it held for all of them). One wrong amount is enough to reject the system. - If the system lacks a 1, some amounts have no answer at all (coins 2 and 5 cannot make 3), and greedy can also get stuck while a solution exists (amount 6 with coins 2 and 5: greedy takes 5 and is left with 1, but 2 + 2 + 2 works).
The DP in words
- State: the amount
astill to be paid. - What one table cell means:
table[a]is the fewest coins that sum to exactlya, or infinity when no combination exists. - Recurrence:
table[a] = 1 + min(table[a - c])over every coinc <= a. Whatever the last coin in an optimal solution is, removing it leaves an optimal solution fora - c(optimal substructure: an optimal solution is built from optimal solutions of smaller parts). - Base case:
table[0] = 0, the empty payment. Everything else starts at infinity. - Fill order:
a = 1, 2, ..., amount, becausetable[a]reads only smaller indices. A second arraylast[a]stores which coin gave the minimum, so the coins can be read back by walking fromamountdown to 0.
The brute force and its call count
Without a table, the recursion f(a) = 1 + min(f(a - c)) re-solves the same amounts again and again. With the coins 1, 3, 4 the number of calls satisfies calls(a) = 1 + sum(calls(a - c) for each coin c <= a), counting the root call, with calls(0) = 1. The run counts them directly and confirms the recurrence gives the same list. Memoisation (storing each result the first time it is computed) cuts the calls that do work to one per amount.
Code
import random
from functools import lru_cache
INF = float("inf")
def greedy(coins, amount):
"""Largest coin that fits, repeatedly. Returns the list of coins, or None if stuck."""
taken = []
for c in sorted(coins, reverse=True):
count, amount = divmod(amount, c) # how many of this coin fit, and what is left
taken += [c] * count
return taken if amount == 0 else None
def brute(coins, amount, counter):
"""Fewest coins by plain recursion; counter[0] counts every call."""
counter[0] += 1
if amount == 0:
return 0
best = INF
for c in coins:
if c <= amount:
best = min(best, 1 + brute(coins, amount - c, counter))
return best
def dp(coins, amount):
"""table[a] = fewest coins that sum to exactly a (INF if impossible)."""
table = [0] + [INF] * amount
last = [None] * (amount + 1) # last[a] = coin used in an optimal way to make a
for a in range(1, amount + 1):
for c in coins:
if c <= a and table[a - c] + 1 < table[a]:
table[a] = table[a - c] + 1
last[a] = c
return table, last
def rebuild(last, amount):
out = []
while amount > 0:
out.append(last[amount])
amount -= last[amount]
return out
def memo_calls(coins, amount):
calls = [0]
@lru_cache(maxsize=None)
def f(a):
calls[0] += 1
if a == 0:
return 0
return min([1 + f(a - c) for c in coins if c <= a], default=INF)
f(amount)
return calls[0]
def smallest_counterexample(coins, limit):
for a in range(1, limit + 1):
t, _ = dp(coins, a)
g = greedy(coins, a)
opt = t[a]
if (g is None) != (opt == INF) or (g is not None and len(g) != opt):
return a
return None
def is_canonical(coins):
"""True when greedy is optimal for every amount (coins must include 1).
Checks every amount below the sum of the two largest coins."""
top = sorted(coins)[-2:]
return smallest_counterexample(coins, sum(top) - 1) is None
coins, amount = [1, 3, 4], 6
g = greedy(coins, amount)
table, last = dp(coins, amount)
print("coins", coins, "amount", amount)
print("greedy:", g, "->", len(g), "coins")
print("dp :", rebuild(last, amount), "->", table[amount], "coins")
print("amount :", list(range(amount + 1)))
print("table :", table)
print("last :", last)
print()
print("brute-force calls for coins [1, 3, 4], amount 0..12 (root call counted):")
row = []
for a in range(13):
c = [0]
brute(coins, a, c)
row.append(c[0])
print("brute :", row)
print("memoised:", [memo_calls(tuple(coins), a) for a in range(13)])
rec = [1]
for a in range(1, 13):
rec.append(1 + sum(rec[a - c] for c in coins if c <= a))
print("recurrence calls(a) = 1 + sum calls(a - c):", rec == row)
print()
for cs in ([1, 5, 10, 25], [1, 3, 4], [1, 5, 10, 20, 25], [1, 15, 25], [2, 5]):
ce = smallest_counterexample(cs, 200)
print(cs, "smallest amount where greedy is not optimal (checked to 200):", ce)
for cs in ([1, 5, 10, 25], [1, 3, 4], [1, 5, 10, 20, 25], [1, 15, 25]):
print(cs, "is_canonical:", is_canonical(cs))
for base in (2, 3, 5):
pw = [base ** i for i in range(5)]
print(pw, "greedy optimal up to 500:", smallest_counterexample(pw, 500) is None)
random.seed(33)
checked = bad = 0
bound_ok = bound_n = 0
for _ in range(400):
k = random.randint(1, 4)
cs = sorted(random.sample(range(1, 13), k))
a = random.randint(0, 20)
ref = brute(cs, a, [0])
t, _ = dp(cs, a)
checked += 1
bad += t[a] != ref
for _ in range(2000):
k = random.randint(2, 5)
cs = [1] + sorted(random.sample(range(2, 40), k - 1))
ce = smallest_counterexample(cs, 2 * cs[-1] + 5)
if ce is not None:
bound_n += 1
bound_ok += ce < cs[-1] + cs[-2]
no_inf = [0] * 4 # mistake: table starts at 0 instead of infinity
for a in range(1, 4):
for c in (2, 5):
if c <= a and no_inf[a - c] + 1 < no_inf[a]:
no_inf[a] = no_inf[a - c] + 1
print()
print("mistake, coins [2, 5] amount 3: table starting at 0 says", no_inf[3], "coins; correct", dp([2, 5], 3)[0][3])
print("dp vs brute force on", checked, "seeded cases (amount 0 and unreachable amounts included): mismatches", bad)
print("systems with a counterexample:", bound_n, "; smallest one below sum of two largest coins in", bound_ok)
Output:
coins [1, 3, 4] amount 6
greedy: [4, 1, 1] -> 3 coins
dp : [3, 3] -> 2 coins
amount : [0, 1, 2, 3, 4, 5, 6]
table : [0, 1, 2, 1, 1, 2, 2]
last : [None, 1, 1, 3, 4, 1, 3]
brute-force calls for coins [1, 3, 4], amount 0..12 (root call counted):
brute : [1, 2, 3, 5, 9, 15, 24, 39, 64, 104, 168, 272, 441]
memoised: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
recurrence calls(a) = 1 + sum calls(a - c): True
[1, 5, 10, 25] smallest amount where greedy is not optimal (checked to 200): None
[1, 3, 4] smallest amount where greedy is not optimal (checked to 200): 6
[1, 5, 10, 20, 25] smallest amount where greedy is not optimal (checked to 200): 40
[1, 15, 25] smallest amount where greedy is not optimal (checked to 200): 30
[2, 5] smallest amount where greedy is not optimal (checked to 200): 6
[1, 5, 10, 25] is_canonical: True
[1, 3, 4] is_canonical: False
[1, 5, 10, 20, 25] is_canonical: False
[1, 15, 25] is_canonical: False
[1, 2, 4, 8, 16] greedy optimal up to 500: True
[1, 3, 9, 27, 81] greedy optimal up to 500: True
[1, 5, 25, 125, 625] greedy optimal up to 500: True
mistake, coins [2, 5] amount 3: table starting at 0 says 0 coins; correct inf
dp vs brute force on 400 seeded cases (amount 0 and unreachable amounts included): mismatches 0
systems with a counterexample: 1298 ; smallest one below sum of two largest coins in 1298
Reading the output
- Greedy returns
[4, 1, 1](3 coins); the table givestable[6] = 2andlastrebuilds[3, 3]. - Row
tablefor amounts 0 to 6 is[0, 1, 2, 1, 1, 2, 2]. Cell 6 comes from1 + min(table[5], table[3], table[2]) = 1 + min(2, 1, 2) = 2, the coin 3 winning. - Brute-force calls grow 1, 2, 3, 5, 9, 15, 24, ... up to 441 at amount 12, about 1.6 times larger per step at the end (441 / 272 = 1.62). The memoised body runs 13 times for amount 12 (one per amount from 0 to 12).
- Random check: 400 seeded cases (1 to 4 coins from 1..12, amounts 0..20) agree with exhaustive recursion, including amount 0 (answer 0) and amounts no combination can make (answer infinity).
- Systems where greedy first fails:
[1, 5, 10, 20, 25]at 40 (greedy 25 + 10 + 5 is three coins, 20 + 20 is two) and[1, 15, 25]at 30 (greedy 25 + 1 x 5 is six coins, 15 + 15 is two).
Complexity
- DP: time
O(amount * k)forkcoin types, spaceO(amount)fortableandlast. At amount 0 the loop does nothing and the table is[0]. - Greedy:
O(k log k)to sort thekcoin types plus onedivmodper coin type (the number of coins of that type and the remainder in one step), but it is only correct on canonical systems. Building the returned list costs one append per coin handed over. - Brute force: the call counts above grow roughly exponentially in the amount.
- Memory note:
amountcan be large (10^9 makes the table impractical); the table is then the wrong tool.
Common mistakes
- Initialising the table to 0 instead of infinity, so unreachable amounts look free: the run prints 0 coins for amount 3 with coins 2 and 5, where the correct answer is infinity.
- Returning infinity to the caller instead of reporting "impossible".
- Claiming greedy works because it worked on the US coins; one counterexample is enough to disprove it, and passing examples prove nothing.
Running the code
docker run --rm -v "$PWD":/w -w /w python:3.12 python greedy_coins.py
Save the listing as greedy_coins.py; it uses only the standard library.
Unlock Full Question Bank
Get access to all 43 Dynamic Programming interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.