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 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).
You can climb a staircase of n steps, taking 1 or 2 steps at a time. Write a function that returns the number of distinct ways to reach the top. State your recurrence and base cases, and give the time and space complexity of your version. Can you get the space down to constant?
Sample Answer
The idea
Every way to climb is a sequence of 1s and 2s that adds up to n. Look only at the last move: it was either a 1-step from stair n-1 or a 2-step from stair n-2. Those two groups do not overlap and together cover every climb, so the count for n is the count for n-1 plus the count for n-2. That is a recurrence (a formula that defines each value from smaller ones), and the numbers it produces are the Fibonacci numbers: the sequence 1, 1, 2, 3, 5, 8, 13, ... in which every term is the sum of the two before it.
The five things to state
- What one cell means.
ways[i]is the number of different sequences of 1-steps and 2-steps whose total is exactly i. - The transition.
ways[i] = ways[i-1] + ways[i-2]. Every sequence for i ends in 1 (the rest is any sequence for i-1) or ends in 2 (the rest is any sequence for i-2), and never both, so nothing is missed or counted twice. - Base cases.
ways[0] = 1(the empty sequence: you are already at the start) andways[1] = 1(just[1]). The recurrence needs two earlier cells, so it can only start at i = 2. - Fill order. Ascending i, because each cell reads two smaller indices.
- Where the answer is.
ways[n]. For n = 5 it is 8, and the filled table and the list of all eight sequences in the output below show why.
Brute force first
Plain recursion ways(n) = ways(n-1) + ways(n-2) recomputes the same subproblems again and again. Counting every call, the root included, gives 15 calls for n = 5, 177 for n = 10, 21,891 for n = 20 and 2,692,537 for n = 30. Each call count is exactly 2 * ways(n) - 1, so the work grows like the answer itself, roughly 1.6 times per extra stair. The memoized version (memoization means remembering the result for each argument so it is computed once) makes 2n - 1 calls: 9, 19, 39 and 59 for the same inputs. The table version removes the recursion altogether.
The code
import random
calls = 0
def ways_brute(n):
"""Plain recursion: ways(n) = ways(n-1) + ways(n-2)."""
global calls
calls += 1
if n <= 1:
return 1
return ways_brute(n - 1) + ways_brute(n - 2)
def ways_memo(n, memo=None, counter=None):
"""Same recursion, but each n is computed once."""
if memo is None:
memo, counter = {}, [0]
counter[0] += 1
if n <= 1:
return 1, counter[0]
if n not in memo:
a, _ = ways_memo(n - 1, memo, counter)
b, _ = ways_memo(n - 2, memo, counter)
memo[n] = a + b
return memo[n], counter[0]
def ways_table(n):
"""ways[i] = number of 1-or-2-step sequences that sum to exactly i."""
ways = [0] * (n + 1)
ways[0] = 1 # the empty sequence
if n >= 1:
ways[1] = 1
for i in range(2, n + 1):
ways[i] = ways[i - 1] + ways[i - 2]
return ways
def ways_const_space(n):
prev2, prev1 = 1, 1 # ways[0], ways[1]
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1 # ways[1] when n == 1, ways[0] when n == 0 is also 1
def ways_const_space_wrong(n):
prev2, prev1 = 1, 1
for _ in range(2, n + 1):
prev2 = prev1 # overwrites prev2 first
prev1 = prev1 + prev2 # now adds prev1 to itself
return prev1
def enumerate_sequences(n):
if n == 0:
return [[]]
out = []
for step in (1, 2):
if step <= n:
out += [[step] + rest for rest in enumerate_sequences(n - step)]
return out
n = 5
print("filled table for n=5:", ways_table(n))
print("all sequences for n=5:", enumerate_sequences(5))
for n in (5, 10, 20, 30):
calls = 0
ways_brute(n)
value, memo_calls = ways_memo(n)
print(f"n={n:2d} ways={value:7d} brute_calls={calls:8d} memo_calls={memo_calls}")
print("n=0 ->", ways_const_space(0), " n=1 ->", ways_const_space(1), " n=2 ->", ways_const_space(2))
print("n=5 correct update:", ways_const_space(5), " wrong update order:", ways_const_space_wrong(5))
random.seed(7)
for _ in range(300):
n = random.randint(0, 18)
expected = len(enumerate_sequences(n))
assert ways_table(n)[n] == ways_const_space(n) == ways_memo(n)[0] == expected
print("300 random n in 0..18 agree with explicit enumeration")
fib_a, fib_b = 1, 1 # F(1), F(2)
for n in range(0, 40):
assert ways_const_space(n) == fib_a # ways(n) is the Fibonacci number F(n+1)
fib_a, fib_b = fib_b, fib_a + fib_b
print("ways(n) equals the Fibonacci number F(n+1) for n in 0..39")
print("ratio ways(30) / ways(29) =", round(ways_const_space(30) / ways_const_space(29), 6),
"| (1 + sqrt(5)) / 2 =", round((1 + 5 ** 0.5) / 2, 6))
n = 0
while ways_const_space(n) <= 2**63 - 1:
n += 1
print("first n whose count exceeds a signed 64-bit integer:", n, "| ways(n-1) =", ways_const_space(n - 1))
Output:
filled table for n=5: [1, 1, 2, 3, 5, 8]
all sequences for n=5: [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [1, 2, 2], [2, 1, 1, 1], [2, 1, 2], [2, 2, 1]]
n= 5 ways= 8 brute_calls= 15 memo_calls=9
n=10 ways= 89 brute_calls= 177 memo_calls=19
n=20 ways= 10946 brute_calls= 21891 memo_calls=39
n=30 ways=1346269 brute_calls= 2692537 memo_calls=59
n=0 -> 1 n=1 -> 1 n=2 -> 2
n=5 correct update: 8 wrong update order: 16
300 random n in 0..18 agree with explicit enumeration
ways(n) equals the Fibonacci number F(n+1) for n in 0..39
ratio ways(30) / ways(29) = 1.618034 | (1 + sqrt(5)) / 2 = 1.618034
first n whose count exceeds a signed 64-bit integer: 92 | ways(n-1) = 7540113804746346429
Reading the output
- The sequence grows by a nearly constant factor: the ratio of one term to the one before it settles at (1 + sqrt(5)) / 2, about 1.618 (the
ratioline). That is where the 1.618 in the plain-recursion row of the table below and the "roughly 1.6 times per extra stair" above come from. - The filled table
[1, 1, 2, 3, 5, 8]isways[0]toways[5]; its last cell is the answer 8, and the eight listed sequences are all of them. ways(n)equals the Fibonacci number F(n+1), where F(1) = F(2) = 1. The check loop asserts that for every n from 0 to 39.- Constant space: only
ways[i-1]andways[i-2]are ever read, so two variables replace the list. The update must be a simultaneous assignmentprev2, prev1 = prev1, prev1 + prev2. The wrong version first overwritesprev2withprev1and then addsprev1to itself, so every step doubles and n = 5 prints 16 instead of 8. - The random check compares the table, the memoized version and the constant-space version against explicit enumeration of every sequence on 300 seeded cases with n from 0 to 18.
Complexity
| Version | States x work per state | Time | Space |
|---|---|---|---|
| Plain recursion | about 2 * ways(n) calls x O(1) | O(1.618^n) | O(n) call stack |
| Memoized | n + 1 states x O(1) | O(n) | O(n) dictionary and O(n) call depth |
| Table | n + 1 cells x O(1) | O(n) | O(n) |
| Two variables | n steps x O(1) | O(n) | O(1) |
The call stack is the list of function calls that have started but are still waiting for their sub-calls to return, and its depth is how many wait at once; plain recursion and the memoized version both go n calls deep before the first return. On CPython that depth is capped: the memoized version hits the default 1000-frame limit for n near 1000; the loop versions do not.
Edge cases and common mistakes
- n = 0 returns 1 (one way to do nothing) and n = 1 returns 1, as printed. Some problem statements start at n = 1; say which convention you use.
- Python integers never overflow, but in a fixed-width language the count exceeds a signed 64-bit integer at n = 92, as the last line of the output shows. Ask whether a modulus is wanted.
- Updating the two rolling variables one at a time in the wrong order, shown above.
Follow-ups
Allowing steps of 1, 2 or 3 turns the recurrence into a sum of three terms. Forbidding some stairs sets ways[i] = 0 on those stairs. For very large n the same recurrence is a 2 x 2 matrix power, which takes O(log n) multiplications.
Running the code
python3.12 climb_stairs.py
Standard library only. Save the listing as climb_stairs.py and run the command above; it prints exactly the output shown.
That is every published Dynamic Programming question for AI Engineer so far. Browse the other topics in this category, or practice this one interactively.