SyntaxPilot
Courses/Python Coding Questions/Lesson 27
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 27 of 30

Dynamic programming questions

climbing stairscoin change (min coins, greedy fails)longest common subsequence

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

  1. 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).
  2. 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.
  3. Why did ways(5000) with lru_cache crash? The first call must recurse ~5,000 levels before results are cached; Python's default recursion limit is 1,000.
  4. 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.
  5. Time and space of the coin-change table? O(amount × coins) time, O(amount) space.
  6. Subsequence vs substring? A subsequence keeps the order but may skip items; a substring is consecutive.
  7. 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.
  8. How do you recover the actual LCS? Walk back from T[m][n]: diagonal on a match, otherwise towards the larger neighbour.
  9. Why start the coin table at infinity? 0 would mean "free"; infinity means "not possible yet", so min ignores it.
  10. Where is DP used in real software? diff tools, 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_cache makes it O(n) but deep recursion still raises RecursionError; 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.