SyntaxPilot
Courses/Python/Lesson 38
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 · Lesson 38 of 40

Dynamic programming

queued

These are the notes for Python episode 38. Ravi, Raju's delivery boy, climbs stairs one or two at a time, and you want the number of different ways. The natural recursion is correct but explodes: 40 stairs runs out of time, because the same small questions are solved again and again. You invent memoization (remember answers in a dict, or let @cache do it), hit the recursion limit at 5,000 stairs, and invent tabulation (fill a table bottom up with a loop). That is dynamic programming (DP). Then you use it where the obvious answer is wrong — fewest coins, where greedy fails — and in two dimensions for routes on a grid, avoiding the [[0]*n]*m trap. Every program below ran for real (Python 3.13.18).

The problem: Ravi climbs the stairs

Ravi climbs 1 or 2 stairs at a time. For 3 stairs there are 3 ways: 1+1+1, 1+2, 2+1. How many ways for 30 stairs? (A classic interview question, "climbing stairs".)

The key idea: Ravi's last step was either 1 stair (from stair n−1) or 2 stairs (from stair n−2). So

ways(n) = ways(n − 1) + ways(n − 2), with ways(0) = ways(1) = 1.

That sentence becomes recursion directly:

calls = 0

def ways(n):                     # ways to climb n stairs, 1 or 2 at a time
    global calls
    calls += 1
    if n <= 1:
        return 1                 # 0 or 1 stair: one way
    return ways(n - 1) + ways(n - 2)

for n in [3, 10, 20, 30]:
    calls = 0
    print(n, "stairs:", ways(n), "ways,", calls, "calls")

Output:

3 stairs: 3 ways, 5 calls
10 stairs: 89 ways, 177 calls
20 stairs: 10946 ways, 21891 calls
30 stairs: 1346269 ways, 2692537 calls

Correct answers, but the calls explode: ten more stairs, more than a hundred times the calls.

def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

print(ways(32))

Output:

3524578

On the SyntaxPilot compiler, ways(40) shows Time Limit Exceeded: the program is stopped after 8 seconds (on our machine it takes about 11.5 s to finish and prints 165580141).

Why: the call tree

ways(5)
├── ways(4)
│   ├── ways(3)          ← solved here...
│   │   ├── ways(2)
│   │   └── ways(1)
│   └── ways(2)
└── ways(3)              ← ...and again from scratch
    ├── ways(2)
    └── ways(1)

ways(3) is solved twice, ways(2) three times. Every level roughly doubles the calls, so the work is about O(2ⁿ): for 40 stairs, around 331 million calls. These repeated small problems are called overlapping subproblems.

Memoization: remember the answers

Real-life example: "1+1+1+1+1+1 = ?" You count: 6. "Now add one more?" You say 7 instantly — you remembered 6. Saving an answer to reuse it is memoization (from "memo", a note to yourself).

calls = 0
memo = {}                        # n -> answer, remembered

def ways(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    if n in memo:                # solved before? just look it up
        return memo[n]
    memo[n] = ways(n - 1) + ways(n - 2)
    return memo[n]

print(ways(40), "ways,", calls, "calls")
print(ways(100))

Output:

165580141 ways, 79 calls
573147844013817084101

79 calls instead of hundreds of millions. Each n is solved once; every other call is a dict lookup, O(1) on average thanks to hashing (episode 35). Time O(n), space O(n).

@cache does it for you

functools.cache (Python 3.9+; lru_cache(maxsize=None) before that) is a decorator (episode 25) that wraps a function with a memo dict keyed by its arguments.

from functools import cache

@cache                           # Python remembers for us
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

print(ways(100))
print(ways(5000))

Output:

573147844013817084101
Traceback (most recent call last):
  File "main.py", line 10, 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) works, but ways(5000) hits RecursionError: to reach ways(5000) the calls stack up about 5,000 deep before any answer is stored, and Python's limit is about 1,000 (episode 36). Memoization is top-down: it still starts from the big problem.

Tabulation: fill a table bottom up

Start from what you already know — table[0] = table[1] = 1 — and fill each next cell from the two before it, with a plain loop.

i 0 1 2 3 4 5 6 7 8
table[i] 1 1 2 3 5 8 13 21 34
def ways(n):
    table = [0] * (n + 1)        # table[i] = ways to climb i stairs
    table[0] = table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

print(ways(10))
print(ways(100))
print(len(str(ways(5000))), "digits")

Output:

89
573147844013817084101
1045 digits

No recursion, so no limit: 5,000 stairs gives a 1,045-digit answer instantly (Python integers grow as needed). Time O(n). Because each cell needs only the last two, you can even drop the table:

def ways(n):
    a, b = 1, 1                  # ways(i - 2), ways(i - 1)
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print(ways(10), ways(40))

Output:

89 165580141

Space O(1).

What is dynamic programming?

DP works when a problem has:

  1. Overlapping subproblems — the same smaller questions come up again and again.
  2. Optimal substructure — the answer to the big problem is built from answers to smaller ones.
Memoization Tabulation
Direction top-down (start from n) bottom-up (start from the base cases)
Tool recursion + dict / @cache loop + list (table)
Solves only the subproblems it needs every subproblem up to n
Limit recursion depth (~1,000) none
Easiest when the recursion is already written the order of subproblems is clear

Either way, each subproblem is solved once: O(2ⁿ) becomes O(n) for the stairs.

Fewest coins: when greedy is wrong

Raju wants change with the fewest coins. The obvious way, greedy: always take the biggest coin that fits.

def greedy_coins(coins, amount):
    used = []
    for c in sorted(coins, reverse=True):   # biggest coin first
        while amount >= c:
            amount -= c
            used.append(c)
    return used

print(greedy_coins([1, 2, 5, 10], 18))
print(greedy_coins([1, 7, 10], 14))

Output:

[10, 5, 2, 1]
[10, 1, 1, 1, 1]

With normal coins greedy is right. With Raju's arcade tokens worth 1, 7 and 10, change for 14 comes out as five coins, but 7 + 7 is two. Greedy grabbed the 10 because it looked best right now, leaving 4, which only 1s can make. Greedy never looks ahead.

The DP table

best[a] = the fewest coins for amount a. For each amount, try every coin as the last coin: best[a] = min(best[a − c] + 1) over coins c ≤ a.

a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
best[a] 0 1 2 3 4 5 6 1 2 3 1 2 3 4 2

For 14: last coin 1 → best[13] + 1 = 5; last coin 7 → best[7] + 1 = 2; last coin 10 → best[4] + 1 = 5. The minimum is 2.

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount      # best[a] = fewest coins for a
    last = [0] * (amount + 1)        # the coin used last for a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
                last[a] = c
    if best[amount] == INF:
        return None
    used = []
    while amount > 0:                # walk back to see which coins
        used.append(last[amount])
        amount -= last[amount]
    return used

print(min_coins([1, 7, 10], 14))
print(min_coins([1, 2, 5, 10], 18))
print(min_coins([4, 6], 7))

Output:

[7, 7]
[1, 2, 5, 10]
None

last[a] remembers which coin gave the best answer, so walking back from the amount rebuilds the actual coins. float("inf") means "not possible yet"; if it's still infinity at the end, return None. Time O(amount × number of coins), space O(amount).

2D DP: routes on a street grid

Ravi rides through a grid of streets and only goes right or down. How many routes reach the far corner? Cells on the top row or left edge have exactly 1 route; any other cell is reached from above or from the left:

grid[r][c] = grid[r − 1][c] + grid[r][c − 1]

The [[0]n]m trap

grid = [[0] * 4] * 3            # 3 rows, 4 columns?
grid[0][0] = 1
print(grid)

Output:

[[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

All three rows changed! * 3 doesn't copy the row; it makes three references to the same list (like three name boards on one house).

grid = [[0] * 4] * 3
print(grid[0] is grid[1])
fixed = [[0] * 4 for _ in range(3)]
print(fixed[0] is fixed[1])

Output:

True
False

The fix: a new list per row

def routes(rows, cols):
    grid = [[0] * cols for _ in range(rows)]   # a NEW list per row
    for r in range(rows):
        for c in range(cols):
            if r == 0 or c == 0:
                grid[r][c] = 1                  # edge: only one way
            else:
                grid[r][c] = grid[r - 1][c] + grid[r][c - 1]
    for row in grid:
        print(row)
    return grid[rows - 1][cols - 1]

print(routes(3, 4), "routes")

Output:

[1, 1, 1, 1]
[1, 2, 3, 4]
[1, 3, 6, 10]
10 routes

Time and space O(rows × cols).

The 4-step DP recipe

  1. State — say in words what one cell means: "dp[i] = ways to reach stair i", "best[a] = fewest coins for a".
  2. Choice — what was the last step? 1 or 2 stairs; which coin; from above or from the left.
  3. Base cases — the answers you already know: dp[0], the top row.
  4. Order — fill from small to big (or recurse with a memo) and return the final cell.

Signal: a recursive solution that is too slow because it repeats calls → think DP.

Common mistakes

Mistake What you see Why Fix
Plain recursion with repeated calls Time Limit Exceeded (40 stairs) O(2ⁿ): the same subproblems again and again a memo dict or @cache
@cache on a very deep recursion RecursionError: maximum recursion depth exceeded ~5,000 calls stack up before anything is stored tabulation with a loop
Greedy for coin change [10, 1, 1, 1, 1] instead of [7, 7] greedy never looks ahead DP over every amount
grid = [[0] * 4] * 3 every row changes together three references to one list [[0] * 4 for _ in range(3)]
Missing or wrong base case RecursionError, or wrong counts nothing stops the recursion / the table starts wrong write dp[0] (and dp[1]) first
best = [0] * (amount + 1) for a minimum every answer 0 0 already looks "best" start with float("inf"), best[0] = 0

Mini project: Raju's change machine

Compare greedy and DP side by side, flag where greedy uses more coins, count the ways to make an amount, and handle impossible amounts.

def greedy(coins, amount):
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used.append(c)
    return used if amount == 0 else None

def fewest(coins, amount):
    INF = float("inf")
    best, last = [0] + [INF] * amount, [0] * (amount + 1)
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a], last[a] = best[a - c] + 1, c
    if best[amount] == INF:
        return None
    used = []
    while amount:
        used.append(last[amount])
        amount -= last[amount]
    return used

def count_ways(coins, amount):          # combinations, order doesn't matter
    ways = [1] + [0] * amount
    for c in coins:                     # coin loop OUTSIDE: no double counting
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

def machine(coins, amount):
    g, d = greedy(coins, amount), fewest(coins, amount)
    if d is None:
        print(f"Rs {amount} with {coins}: impossible")
        return
    flag = "  <- greedy wastes coins" if g is None or len(g) > len(d) else ""
    print(f"Rs {amount} with {coins}: greedy {g}, DP {d}, {count_ways(coins, amount)} ways{flag}")

machine([1, 7, 10], 14)
machine([1, 2, 5, 10], 18)
machine([4, 6], 7)
machine([4, 6], 12)
# For real input: coins = [int(x) for x in input("coins: ").split()]

Output:

Rs 14 with [1, 7, 10]: greedy [10, 1, 1, 1, 1], DP [7, 7], 4 ways  <- greedy wastes coins
Rs 18 with [1, 2, 5, 10]: greedy [10, 5, 2, 1], DP [1, 2, 5, 10], 31 ways
Rs 7 with [4, 6]: impossible
Rs 12 with [4, 6]: greedy [6, 6], DP [6, 6], 2 ways

Practice

  1. Stairs with steps of 1, 2 or 3. How many ways for 10 stairs?
Solution
def ways3(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        dp[i] = sum(dp[i - s] for s in (1, 2, 3) if i - s >= 0)
    return dp[n]

print(ways3(3), ways3(4), ways3(10))

Output:

4 7 274
  1. How many ways can you make ₹50 from coins 1, 2, 5 and 10 (order doesn't matter)?
Solution
def count_ways(coins, amount):
    ways = [1] + [0] * amount
    for c in coins:
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

print(count_ways([1, 2, 5, 10], 50))
print(count_ways([1, 2], 4))   # 1111, 112, 22

Output:

341
3

Putting the coin loop outside counts each combination once (1+2 and 2+1 are the same).

  1. Grid routes when some streets are blocked (#).
Solution
def routes(city):
    rows, cols = len(city), len(city[0])
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if city[r][c] == "#":
                continue                    # blocked: 0 routes
            if r == 0 and c == 0:
                dp[r][c] = 1
            else:
                up = dp[r - 1][c] if r > 0 else 0
                left = dp[r][c - 1] if c > 0 else 0
                dp[r][c] = up + left
    return dp[-1][-1]

print(routes(["....", "....", "...."]))
print(routes(["....", ".#..", "...."]))

Output:

10
4
  1. Rewrite ways(n) for the stairs with @cache, and find the largest n that works before RecursionError. Then explain why tabulation has no such limit.
Solution
from functools import cache

@cache
def ways(n):
    return 1 if n <= 1 else ways(n - 1) + ways(n - 2)

for n in range(0, 3000, 100):    # growing slowly fills the cache step by step
    ways(n)
print(len(str(ways(2900))), "digits")

Output:

606 digits

Calling with growing n fills the cache gradually, so each call only goes about 100 deep. A single cold call to ways(1000) or more fails. Tabulation uses a loop, which has no depth at all.

Quick quiz

dp = [1, 1]
for i in range(2, 6):
    dp.append(dp[i - 1] + dp[i - 2])
print(dp[5])

Options: 5 · 8 · 13 · 6

Answer

8. dp grows 1, 1, 2, 3, 5, 8, and dp[5] is 8 — the ways to climb 5 stairs.

Interview questions

  1. What is dynamic programming? Solving a problem by combining answers to overlapping subproblems, solving each subproblem once (memoization or tabulation).
  2. Memoization vs tabulation? Memoization is top-down recursion with a cache, and computes only what's needed; tabulation is a bottom-up loop that fills a table, with no recursion limit.
  3. What are the two properties a problem needs for DP? Overlapping subproblems and optimal substructure.
  4. Why does greedy fail for coin change with coins 1, 7, 10? For 14 it takes 10 first and is left with 4 (four 1s, five coins total), while 7 + 7 uses two. Greedy is only correct for special coin systems like 1, 2, 5, 10.
  5. Time complexity of coin change DP? O(amount × number of coins); space O(amount).
  6. How would you reduce the space of the stairs DP? Keep only the last two values: O(1) space.
  7. What's wrong with [[0] * cols] * rows? All rows are the same list object; use a list comprehension.

Glossary

Term Meaning Example
Dynamic programming (DP) Solve each overlapping subproblem once and build the answer from them stairs, coins, grid routes
Subproblem A smaller version of the same question ways(3) inside ways(5)
Overlapping subproblems The same subproblem is needed many times ways(2) three times in ways(5)
Optimal substructure The best answer is built from best answers to smaller parts best[14] from best[7]
Recursion A function that calls itself on a smaller input ways(n - 1) + ways(n - 2)
Call tree A drawing of every call a recursion makes ways(5) → ways(4), ways(3)
O(2ⁿ) Work doubles with every extra input step plain recursive stairs
Memoization Store each answer the first time and look it up after memo[n] = ...
Memo The dict (or cache) holding saved answers memo = {}
functools.cache A decorator that memoizes a function automatically @cache
Decorator A function that wraps another function (episode 25) @cache above def
RecursionError Python stopped a recursion deeper than its limit (~1,000) ways(5000) with @cache
Tabulation Fill a table from the base cases up with a loop table[i] = table[i-1] + table[i-2]
Top-down Start from the big problem and recurse to small ones memoization
Bottom-up Start from the smallest answers and build up tabulation
Base case An answer known without any work ways(0) = ways(1) = 1
State What one cell of the DP means best[a] = fewest coins for a
Transition The rule that computes a cell from smaller cells best[a - c] + 1
Greedy algorithm Always take the choice that looks best right now biggest coin first
float("inf") A value bigger than every number; "not possible yet" best = [0] + [INF] * amount
2D table A list of lists: rows and columns grid[r][c]
Reference A name pointing at an object; several names can share one [[0]*4]*3
List comprehension Build a list with an expression and a loop (episode 16) [[0] * 4 for _ in range(3)]
Time Limit Exceeded The compiler stopped a program that ran too long (8 s here) ways(40) naive

Summary

  • Recursion that repeats the same calls is exponential: O(2ⁿ).
  • Memoization (dict or @cache) remembers answers top-down; tabulation fills a table bottom-up with no recursion limit.
  • DP needs overlapping subproblems and optimal substructure; each subproblem is solved once.
  • Greedy can be wrong; DP tries every choice but each amount once: fewest coins for 14 with 1, 7, 10 is [7, 7].
  • 2D tables need a new list per row: [[0] * cols for _ in range(rows)].
  • Recipe: state → choice → base cases → order.
  • Next episode: design patterns in Python.