Climbing stairs
StopDP table
- CH1 prev2
- CH2 prev1
7/7
Each step's count is the sum of the two before it.
Step through it →Dynamic Programming
Dynamic programming solves each smaller problem once, writes its answer in a table, and builds every bigger answer from cells already filled.
Coin change: the fewest coins that make the amount
StopDP table
CoinsAmount
- CH1 coin 1
- CH2 coin 3
- CH3 coin 4
dp[0] = 0: no coins make 0. Every other amount starts at ∞, which the code stores as 7, more coins than any answer uses.
Typical cost Typically O(n·k) time and space (often reducible to O(k))Full lesson: Coin Change →
When to reach for it
- You're asked for a count, a minimum or maximum, or whether something is possible.
- The answer for n depends on answers for smaller n.
- A plain recursion solves the same subproblem again and again.
- Greedy looks right, but a small example breaks it.
What stays true
Edit distance fills its grid row by row. By the time a cell is written, the three it reads are done, so no cell is computed twice and none waits on a cell below it.
A cell reads only cells already filled
StopDP table
InvariantA cell reads its neighbors above and to the left, which are already final.✓ Holds
- CH1 ↖ keep/replace
- CH2 ↑ delete
- CH3 ← insert
Column 0: turning the first i letters of "helo" into nothing takes i deletes.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Greedy takes 9, then 1 and 1: three coins. The table finds 5 + 6.
Coin change on the inputs that trip it up
StopDP table
- CH1 coin 1
- CH2 coin 5
- CH3 coin 6
- CH4 coin 9
dp[0] = 0: no coins make 0. Every other amount starts at ∞, which the code stores as 12, more coins than any answer uses.
Answer2Steps13
Variants
House robber
StopDP table
- CH1 twoBack
- CH2 oneBack
7/7
Take this house plus the best from two back, or skip it.
Step through it →Maximum subarray
StopDP table
- CH1 current
- CH2 best
10/10
Extend the run that ends here, or start over at this number.
Step through it →Word break
StopDP table
- CH1 j
15/15
A boundary is reachable if a word ends there from a reachable one.
Step through it →The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Coin change: the fewest coins that make the amount
StopDP table
- CH1 coin 1
- CH2 coin 3
- CH3 coin 4
dp[0] = 0: no coins make 0. Every other amount starts at ∞, which the code stores as 7, more coins than any answer uses.
coin_change.py
def fill(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for a in range(1, amount + 1): for coin in coins: if coin <= a: dp[a] = min(dp[a], 1 + dp[a - coin]) return dpdef coin_change(coins, amount): dp = fill(coins, amount) return dp[amount] if dp[amount] <= amount else -1