Algorithms from zero
Dynamic programming: code reading
Crux Read real DP snippets, find the cache bug, the wrong state, the unsafe space optimization, and the true complexity — the diagnosis a senior makes before trusting any DP.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skyDP bugs are silent — they return a confidently wrong number, not a crash. Read each snippet, predict what it actually computes, and pick the fix a senior would make first.
Goal
Practise the loop you run on every DP: check the cache key matches the full state, check the transition covers every choice, check a space optimization does not destroy a value it still needs, and read the real complexity off the loops.
Snippet 1 — the memo that never hits
def lcs(a, b):
memo = {}
def go(i, j):
if i == len(a) or j == len(b):
return 0
if a in memo: # bug: keying on the wrong thing
return memo[a]
if a[i] == b[j]:
res = 1 + go(i + 1, j + 1)
else:
res = max(go(i + 1, j), go(i, j + 1))
memo[a] = res
return res
return go(0, 0) Quiz
Completed
This memoized LCS is both wrong and slow. What is the defect and the fix?
Heads-up An empty subsequence has length 0; returning 1 would overcount. The base case is correct — the cache key is the defect.
Heads-up LCS takes the better of the two skip options, so max is right. Summing would double-count overlapping subsequences. The bug is the cache key.
Heads-up Depth here is at most len(a)+len(b), which is fine for normal inputs. The real bug is keying the cache on a instead of (i, j).
Snippet 2 — the coin-change state
def min_coins(coins, amount):
# one coin per denomination, no reuse
dp = [0] + [float('inf')] * amount
for c in coins:
for x in range(amount, c - 1, -1): # capacity downward
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1 Quiz
Completed
The author wants UNLIMITED use of each coin (classic coin change). Does this 1D code do that, and what does the iteration direction control?
Heads-up Direction is exactly what separates the two variants. Downward (0/1) forbids reusing a coin within one pass; upward (unbounded) allows it. Here downward gives the wrong, at-most-once answer.
Heads-up dp[0]=0 is correct: zero coins make amount 0. The defect is the downward loop direction, which silently limits each coin to one use.
Heads-up Coin order does not affect correctness of this DP. The defect is the loop direction selecting the 0/1 semantics instead of unbounded.
Snippet 3 — the rolling-row optimization
def edit_distance(a, b):
n, m = len(a), len(b)
prev = list(range(m + 1)) # row for i = 0
for i in range(1, n + 1):
cur = [i] + [0] * m # cur[0] = i
for j in range(1, m + 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[m] Quiz
Completed
This edit-distance code rolls the 2D table down to two rows. Is the space optimization correct, and what is the dependency that makes it safe?
Heads-up Each cell reads only the previous row and the current row's left neighbor, so two rows suffice. The full table is only needed if you must reconstruct the actual edit script.
Heads-up cur and prev are separate arrays, so writing cur[j-1] never touches prev[j-1]. The diagonal prev[j-1] stays intact for the next column. The optimization is safe.
Heads-up Nothing is approximated; the three reads (prev[j], cur[j-1], prev[j-1]) are the exact same values the full table holds. Same answer, less memory.
Snippet 4 — the interval-DP loops
def interval_cost(n, weight):
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1): # interval length
for i in range(0, n - length + 1): # left endpoint
j = i + length - 1 # right endpoint
best = float('inf')
for k in range(i, j): # split point
best = min(best, dp[i][k] + dp[k + 1][j] + weight(i, k, j))
dp[i][j] = best
return dp[0][n - 1] Quiz
Completed
What is the time and space complexity of this interval DP, and where does the dominant cost come from?
Heads-up There are three nested loops: length, left endpoint, and split point k. The inner split scan is what pushes it to O(n^3), not O(n^2).
Heads-up Time is O(n^3), but space is only the dp table, which is n-by-n, so O(n^2). There is no third dimension stored.
Heads-up Splits are tried, but each (i, j) is computed once and cached in dp, so it is polynomial. The exponential figure is the naive recursion without the table.
Recap
Four checks catch most DP defects: the cache key must equal the full subproblem state (Snippet 1 keyed on the wrong variable); the transition and loop direction must match the intended semantics (Snippet 2 — downward is 0/1, upward is unbounded); a rolling-row space cut is safe only when each cell reads just the previous row and the current row’s neighbors (Snippet 3); and the real complexity is the product of the loop bounds — O(n^2) states times O(n) work per state is O(n^3) (Snippet 4). Read the loops, do not trust the comment.