These are the notes for Python Coding Questions, episode 27: dynamic programming. Three classic interview questions: climbing stairs, coin change (where the greedy answer is wrong) and the longest common subsequence.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Timings change from machine to machine and run to run; what matters is how they grow.
Words for today:
- Subproblem: a smaller version of the same question ("ways to climb 4 stairs" inside "ways to climb 5 stairs").
- Overlapping subproblems: the same subproblem is needed again and again.
- Memoization: storing each subproblem's answer the first time, then looking it up (from memo, a note to yourself). Also called top-down DP.
- Tabulation: filling a table from the smallest subproblem up to the one you want. Also called bottom-up DP.
- Dynamic programming (DP): solving a problem by combining answers to overlapping subproblems, each solved only once.
- Greedy algorithm: always take the move that looks best right now, never going back.
Q1: Climbing stairs
Real-life example: the stairs to your flat. You go up 1 or 2 stairs at a time. How many different ways are there to climb n stairs?
Think backwards: your last step started either 1 stair below the top or 2 stairs below. So
ways(n) = ways(n - 1) + ways(n - 2), with ways(0) = ways(1) = 1.
Attempt 1: plain recursion
import time
def ways(n):
if n <= 1:
return 1
return ways(n - 1) + ways(n - 2) # last step: 1 or 2
print([ways(n) for n in range(1, 8)])
for n in [28, 31, 34]:
start = time.perf_counter()
w = ways(n)
print(n, w, f"{time.perf_counter() - start:.2f} s")
Output:
[1, 2, 3, 5, 8, 13, 21]
28 514229 0.06 s
31 2178309 0.48 s
34 9227465 2.00 s
Correct (1, 2, 3, 5, 8, 13, 21: the Fibonacci numbers), but every 3 extra stairs ≈ 4× the time. Each call makes two more calls, so the number of calls roughly doubles per level: exponential time, about O(1.6ⁿ). Most calls are repeats: ways(32) is computed twice, ways(31) three times, ways(30) five times...
Attempt 2: memoization with lru_cache
functools.lru_cache remembers every result of a function by its arguments (you met it in episode 3). maxsize=None means it never forgets.
from functools import lru_cache
@lru_cache(maxsize=None)
def ways(n):
if n <= 1:
return 1
return ways(n - 1) + ways(n - 2)
print(ways(31), ways(100))
print(ways.cache_info())
print(ways(5000))
Output:
2178309 573147844013817084101
CacheInfo(hits=99, misses=101, maxsize=None, currsize=101)
Traceback (most recent call last):
File "main.py", line 11, in <module>
print(ways(5000))
~~~~^^^^^^
File "main.py", line 7, in ways
return ways(n - 1) + ways(n - 2)
~~~~^^^^^^^
File "main.py", line 7, in ways
return ways(n - 1) + ways(n - 2)
~~~~^^^^^^^
File "main.py", line 7, in ways
return ways(n - 1) + ways(n - 2)
~~~~^^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
ways(100) is instant: 101 misses (one per n from 0 to 100) and 99 hits (every other call was a lookup). But ways(5000) crashes with RecursionError: maximum recursion depth exceeded: the very first call still has to go about 5,000 calls deep before anything is in the cache, and Python's default limit (sys.getrecursionlimit()) is 1,000.
The fix: bottom-up with two variables
Start from the bottom and walk up. Each answer needs only the two before it, so keep two variables.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| ways(n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
import time
def ways(n):
a, b = 1, 1 # ways(0), ways(1)
for _ in range(n - 1):
a, b = b, a + b # slide: keep only the last two
return b
print([ways(n) for n in range(1, 8)], ways(0))
print(ways(100))
start = time.perf_counter()
big = ways(5000)
print(len(str(big)), "digits", f"{time.perf_counter() - start:.4f} s")
Output:
[1, 2, 3, 5, 8, 13, 21] 1
573147844013817084101
1045 digits 0.0005 s
O(n) time, O(1) space, and no recursion, so no depth limit. Python's integers have no overflow, so the 1,045-digit answer is exact.
| Version | Time | Space | Problem |
|---|---|---|---|
| plain recursion | exponential | O(n) stack | too slow after ~35 stairs |
@lru_cache (top-down) |
O(n) | O(n) cache + stack | RecursionError for big n |
| two variables (bottom-up) | O(n) | O(1) | none |
Q2: Coin change (fewest coins)
Real-life example: a shopkeeper gives 18 rupees in change with coins 10, 5, 2 and 1, using the fewest coins.
Attempt 1: greedy (biggest coin first)
def greedy(coins, amount):
count = 0
for c in sorted(coins, reverse=True): # biggest first
count += amount // c
amount %= c
return count if amount == 0 else -1
print(greedy([1, 2, 5, 10], 18))
print(greedy([1, 3, 4], 6))
print(greedy([5, 10], 3))
Output:
4
3
-1
18 → 10 + 5 + 2 + 1 = 4 coins, correct. 3 with only 5s and 10s → -1 (impossible), correct. But with coins 4, 3, 1 and amount 6, greedy says 4 + 1 + 1 = 3 coins, while 3 + 3 = 2 coins. Greedy is wrong: taking the 4 looked best, but it left 2 rupees that cost two more coins, and greedy never goes back on a choice. (Greedy happens to work for "canonical" coin systems such as Indian coins; it is not safe in general.)
Attempt 2: try every last coin (recursion)
The last coin handed over is some coin c, so fewest(x) = 1 + fewest(x - c) for the best c, and fewest(0) = 0.
import time
def min_coins(coins, amount):
if amount == 0:
return 0
best = float("inf")
for c in coins:
if c <= amount:
best = min(best, 1 + min_coins(coins, amount - c))
return best
print(min_coins([1, 3, 4], 6))
for amount in [26, 30, 34]:
start = time.perf_counter()
min_coins([1, 3, 4], amount)
print(amount, f"{time.perf_counter() - start:.2f} s")
Output:
2
26 0.27 s
30 1.04 s
34 5.35 s
Correct (2), but +4 rupees ≈ 6-8× the time: each call makes up to three calls, and the same amounts are solved again and again. Exponential again.
The fix: a table from 0 up to the amount
best[x] = fewest coins for x. best[0] = 0, every other cell starts at infinity (float("inf"): "not possible yet").
best[x] = min(best[x - c] + 1) over every coin c ≤ x. Every cell it reads is already filled.
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| best[x] (coins 1, 3, 4) | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
def coin_table(coins, amount):
INF = float("inf")
best = [0] + [INF] * amount # best[x]: fewest coins for x
for x in range(1, amount + 1):
for c in coins:
if c <= x:
best[x] = min(best[x], best[x - c] + 1)
return best
def min_coins(coins, amount):
best = coin_table(coins, amount)[amount]
return best if best != float("inf") else -1
print(coin_table([1, 3, 4], 6))
print(min_coins([1, 3, 4], 6), min_coins([1, 2, 5, 10], 18))
print(min_coins([5, 10], 3), min_coins([2], 0), min_coins([7], 14))
print(min_coins([1, 3, 4], 10_000))
Output:
[0, 1, 2, 1, 1, 2, 2]
2 4
-1 0 2
2500
O(amount × number of coins) time, O(amount) space. 10,000 rupees takes 30,000 small steps. If the last cell is still infinity, no mix of coins works: return -1.
Q3: Longest common subsequence (LCS)
Real-life example: Mom's list is milk, bread, eggs, tea, rice; the shop's bill is bread, butter, tea, jam, rice. The longest list of items in both, in the same order is bread, tea, rice (3).
A subsequence keeps the order but may skip items ("ACE" is a subsequence of "ABCDE"; "EA" is not). A substring must be consecutive. git diff and file-compare tools are built on the LCS idea. A prefix is the start of a string: a[:i].
Attempt 1: recursion on the last characters
- If the last characters match, they are part of an LCS:
1 + lcs(a[:-1], b[:-1]). - Otherwise drop the last character of one string or the other and keep the better answer.
import time
def lcs(a, b):
if not a or not b:
return 0
if a[-1] == b[-1]:
return 1 + lcs(a[:-1], b[:-1]) # same last: keep it
return max(lcs(a[:-1], b), lcs(a, b[:-1]))
print(lcs("ABCBDAB", "BDCABA"))
for n in [8, 10, 12]:
x, y = "AB" * (n // 2), "CD" * (n // 2) # no match
start = time.perf_counter()
lcs(x, y)
print(n, f"{time.perf_counter() - start:.2f} s")
Output:
4
8 0.01 s
10 0.08 s
12 0.73 s
Correct (4: one answer is "BCBA"), but +2 letters ≈ 15× the time. With no matches every call splits in two, and the same pairs of prefixes come up again and again.
The fix: a 2D table, one cell per pair of prefixes
T[i][j] = LCS length of a[:i] and b[:j]. Row 0 and column 0 are 0 (an empty string has nothing in common).
a[i-1] == b[j-1]→T[i][j] = T[i-1][j-1] + 1(diagonal + 1)- otherwise →
T[i][j] = max(T[i-1][j], T[i][j-1])(up or left)
The table for "chai" (rows) and "chaat" (columns):
| "" | c | h | a | a | t | |
|---|---|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 | 0 | 0 |
| c | 0 | 1 | 1 | 1 | 1 | 1 |
| h | 0 | 1 | 2 | 2 | 2 | 2 |
| a | 0 | 1 | 2 | 3 | 3 | 3 |
| i | 0 | 1 | 2 | 3 | 3 | 3 |
import time
def lcs(a, b):
m, n = len(a), len(b)
T = [[0] * (n + 1) for _ in range(m + 1)] # lcs(a[:i], b[:j])
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
T[i][j] = T[i - 1][j - 1] + 1
else:
T[i][j] = max(T[i - 1][j], T[i][j - 1])
return T[m][n]
print(lcs("ABCBDAB", "BDCABA"), lcs("chai", "chaat"))
print(lcs("", "abc"), lcs("abc", "xyz"), lcs("same", "same"))
x, y = "AB" * 1000, "CD" * 1000
start = time.perf_counter()
print(lcs(x, y), f"{time.perf_counter() - start:.2f} s")
Output:
4 3
0 0 4
0 0.89 s
O(m·n) time and space: 2,000 × 2,000 = 4 million cells in about half a second. The recursion would never finish.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| plain recursion with repeated subproblems | +3 stairs → 4× the time | the same subproblem is solved again and again | memoize or build a table |
@lru_cache on a very deep recursion |
RecursionError: maximum recursion depth exceeded |
still ~n calls deep | bottom-up loop |
@lru_cache with a list argument |
TypeError: unhashable type: 'list' |
the cache key must be hashable | pass a tuple |
| greedy coin change | 3 coins for 6, best is 2 | never goes back on a choice | DP: try every last coin |
best = [0] * (amount + 1) |
every amount "needs 0 coins" | 0 means "free", not "unknown" | start at float("inf") |
T = [[0] * (n + 1)] * (m + 1) |
every row changes together | the same row object m + 1 times | [[0] * (n + 1) for _ in range(m + 1)] |
| forgetting the base case | wrong answer for n = 0 or amount = 0 | the smallest case is special | write the base case first |
The lru_cache list trap:
from functools import lru_cache
@lru_cache(maxsize=None)
def total(prices):
return sum(prices)
print(total((10, 20, 30)))
print(total([10, 20, 30]))
Output:
60
Traceback (most recent call last):
File "main.py", line 8, in <module>
print(total([10, 20, 30]))
~~~~~^^^^^^^^^^^^^^
TypeError: unhashable type: 'list'
The coin table started at 0 instead of infinity (every amount looks free):
best = [0] * 7 # wrong start: 0 means "free"
for x in range(1, 7):
for c in [1, 3, 4]:
if c <= x:
best[x] = min(best[x], best[x - c] + 1)
print(best)
Output:
[0, 0, 0, 0, 0, 0, 0]
The 2D table made by multiplying a list:
T = [[0] * 3] * 2
T[0][0] = 9
print(T)
T = [[0] * 3 for _ in range(2)]
T[0][0] = 9
print(T)
Output:
[[9, 0, 0], [9, 0, 0]]
[[9, 0, 0], [0, 0, 0]]
Your turn: print the common items (solution)
Question: return the longest common subsequence itself, not just its length.
Idea: fill the table as before, then walk back from T[m][n]: on a match, take the item and go diagonally; otherwise go towards the bigger neighbour (up or left). The items come out backwards, so reverse them. It works for strings and for lists.
def lcs_text(a, b):
m, n = len(a), len(b)
T = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
T[i][j] = T[i - 1][j - 1] + 1
else:
T[i][j] = max(T[i - 1][j], T[i][j - 1])
out, i, j = [], m, n # walk back from the corner
while i and j:
if a[i - 1] == b[j - 1]: # a match: take it, go diagonal
out.append(a[i - 1])
i, j = i - 1, j - 1
elif T[i - 1][j] >= T[i][j - 1]: # else go to the bigger neighbour
i -= 1
else:
j -= 1
return out[::-1]
print("".join(lcs_text("ABCBDAB", "BDCABA")), "".join(lcs_text("chai", "chaat")))
mom = ["milk", "bread", "eggs", "tea", "rice"]
bill = ["bread", "butter", "tea", "jam", "rice"]
print(lcs_text(mom, bill), lcs_text([], bill))
Output:
BCBA cha
['bread', 'tea', 'rice'] []
Mini project: a ticket machine that gives change
The coin table plus one more list, last[x] (the last coin used for x), tells you which coins to give, not just how many.
def make_change(coins, amount):
"""Fewest coins for amount, and WHICH coins (or None if impossible)."""
INF = float("inf")
best = [0] + [INF] * amount
last = [None] * (amount + 1) # the last coin used for x
for x in range(1, amount + 1):
for c in coins:
if c <= x and best[x - c] + 1 < best[x]:
best[x] = best[x - c] + 1
last[x] = c
if best[amount] == INF:
return None
used, x = [], amount
while x > 0: # follow the last coins back
used.append(last[x])
x -= last[x]
return sorted(used, reverse=True)
print(make_change([1, 3, 4], 6)) # greedy would say [4, 1, 1]
print(make_change([1, 2, 5, 10, 20], 38))
print(make_change([5, 10], 3), make_change([7], 0))
Output:
[3, 3]
[20, 10, 5, 2, 1]
None []
Practice questions (with solutions)
1. Count the ways to make an amount (combinations, order doesn't matter: 1 + 2 + 2 is the same as 2 + 1 + 2).
Solution
ways[x] = number of ways to make x. Loop over the coins outside and the amounts inside, so each combination is counted once (coins inside would count orders separately). O(amount × coins).
def count_ways(coins, amount):
ways = [1] + [0] * amount # 1 way to make 0: no coins
for c in coins: # coins OUTSIDE: combinations
for x in range(c, amount + 1):
ways[x] += ways[x - c]
return ways[amount]
print(count_ways([1, 2, 5], 5), count_ways([2], 3), count_ways([1, 2, 5, 10], 100))
Output:
4 0 2156
2. House robber: take money from houses in a row, but never from two neighbours. What's the most you can take?
Solution
For each house: either take it (then the previous one was skipped) or skip it (keep the best so far). Two variables, O(n) time, O(1) space.
def rob(houses):
take, skip = 0, 0 # best so far if we take / skip the last house
for h in houses:
take, skip = skip + h, max(take, skip)
return max(take, skip)
print(rob([2, 7, 9, 3, 1]), rob([5]), rob([]), rob([2, 1, 1, 2]))
Output:
12 5 0 4
3. Edit distance: the fewest single-letter inserts, deletes and replacements that turn one word into another.
Solution
D[i][j] = edit distance between a[:i] and b[:j]. A match costs nothing (diagonal); otherwise 1 + the best of delete (up), insert (left) and replace (diagonal). O(m·n).
def edit_distance(a, b):
m, n = len(a), len(b)
D = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
D[i][0] = i # delete everything
for j in range(n + 1):
D[0][j] = j # insert everything
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
D[i][j] = D[i - 1][j - 1]
else:
D[i][j] = 1 + min(D[i - 1][j], # delete
D[i][j - 1], # insert
D[i - 1][j - 1]) # replace
return D[m][n]
print(edit_distance("chai", "chaat"), edit_distance("kitten", "sitting"), edit_distance("", "abc"))
Output:
2 3 3
4. Min cost climbing stairs: each stair has a cost; you may start on stair 0 or 1 and climb 1 or 2 at a time. What's the cheapest way past the top?
Solution
Same shape as climbing stairs, with min instead of +. O(n) time, O(1) space.
def min_cost_stairs(cost):
a, b = 0, 0 # cheapest way to stand on step i-2, i-1
for i in range(2, len(cost) + 1):
a, b = b, min(b + cost[i - 1], a + cost[i - 2])
return b
print(min_cost_stairs([10, 15, 20]), min_cost_stairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
Output:
15 6
Quick quiz
What does this print?
def ways(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b
print(ways(6))
(A) 8 (B) 13 (C) 21 (D) 6
Answer
(B). The values go 1, 1, 2, 3, 5, 8, 13 for 0 to 6 stairs.
13
Interview questions
- What makes a problem a good fit for dynamic programming? Overlapping subproblems (the same smaller question again and again) and optimal substructure (the best answer is built from best answers to smaller questions).
- Memoization vs tabulation? Memoization (top-down) keeps the recursion and caches results; easy to write, but uses the call stack. Tabulation (bottom-up) fills a table with loops; no recursion limit, often less memory.
- Why did
ways(5000)withlru_cachecrash? The first call must recurse ~5,000 levels before results are cached; Python's default recursion limit is 1,000. - Why does greedy fail for coins [1, 3, 4] and 6? It takes 4 first and needs 1 + 1, while 3 + 3 uses fewer coins; greedy never revisits a choice.
- Time and space of the coin-change table? O(amount × coins) time, O(amount) space.
- Subsequence vs substring? A subsequence keeps the order but may skip items; a substring is consecutive.
- LCS time and space? O(m·n) for both; the space can be cut to O(min(m, n)) by keeping only two rows if you only need the length.
- How do you recover the actual LCS? Walk back from
T[m][n]: diagonal on a match, otherwise towards the larger neighbour. - Why start the coin table at infinity? 0 would mean "free"; infinity means "not possible yet", so
minignores it. - Where is DP used in real software?
difftools, spell checkers (edit distance), route planning, text justification, bioinformatics (DNA alignment).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Subproblem | A smaller version of the same question | ways(4) inside ways(5) |
| Overlapping subproblems | The same subproblem is needed many times | ways(3) asked again and again |
| Optimal substructure | The best answer is built from best smaller answers | best[x] = best[x - c] + 1 |
| Dynamic programming (DP) | Solving each overlapping subproblem once and combining | all three questions |
| Memoization (top-down) | Store each answer the first time, look it up after | @lru_cache(maxsize=None) |
lru_cache |
functools decorator that caches results by arguments | ways.cache_info() |
| Cache hit / miss | Found in the cache / had to be computed | 99 hits, 101 misses |
| Tabulation (bottom-up) | Fill answers from the smallest case upwards | the coin table |
| Base case | The smallest case, answered directly | ways(0) = 1, best[0] = 0 |
| Recursion depth | How many calls are waiting at once | limit about 1,000 |
RecursionError |
Raised when the depth limit is passed | ways(5000) with recursion |
| Exponential time | Time multiplies with every step of n | plain ways(n) |
| Greedy algorithm | Always take the best-looking move now | biggest coin first |
float("inf") |
A value bigger than any number | "not possible yet" |
| Hashable | Usable as a dict key / cache key | tuples yes, lists no |
| Subsequence | Items in order, skipping allowed | "BCBA" in "ABCBDAB" |
| Substring | Consecutive characters | "BCB" in "ABCBDAB" |
| Prefix | The start of a string | a[:i] |
| LCS | Longest common subsequence | 4 for "ABCBDAB", "BDCABA" |
| 2D table | A list of lists, T[i][j] |
the LCS table |
| O(m·n) | Time grows with the product of two lengths | LCS of two strings |
Summary
- Dynamic programming = overlapping subproblems, each solved once and remembered.
- Climbing stairs:
ways(n) = ways(n-1) + ways(n-2). Plain recursion is exponential;@lru_cachemakes it O(n) but deep recursion still raisesRecursionError; bottom-up with two variables is O(n) time, O(1) space. - Coin change: greedy (biggest coin first) can be wrong; the table
best[x] = min(best[x - c] + 1), starting at infinity, is always right: O(amount × coins). - Longest common subsequence: a 2D table, diagonal + 1 on a match, otherwise max(up, left): O(m·n).
- Next episode: file and data questions: count the words in a file, the top-k frequent words with
heapq, and totalling a column of a CSV file with bad rows.