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:
- Overlapping subproblems — the same smaller questions come up again and again.
- 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
- State — say in words what one cell means: "
dp[i]= ways to reach stair i", "best[a]= fewest coins for a". - Choice — what was the last step? 1 or 2 stairs; which coin; from above or from the left.
- Base cases — the answers you already know:
dp[0], the top row. - 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
- 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
- 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).
- 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
- Rewrite
ways(n)for the stairs with@cache, and find the largest n that works beforeRecursionError. 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
- What is dynamic programming? Solving a problem by combining answers to overlapping subproblems, solving each subproblem once (memoization or tabulation).
- 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.
- What are the two properties a problem needs for DP? Overlapping subproblems and optimal substructure.
- 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.
- Time complexity of coin change DP? O(amount × number of coins); space O(amount).
- How would you reduce the space of the stairs DP? Keep only the last two values: O(1) space.
- 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.