Dynamic programming I
Dynamic programming is the paradigm for problems with overlapping subproblems and optimal substructure: the same smaller problems recur, so we solve each once and reuse the answer. This lesson builds the mental method for seeing a DP — defining a state, deriving a recurrence, choosing memoization vs tabulation — through the canonical 1-D problems: climbing stairs, house robber, coin change and longest increasing subsequence.
Learning objectives
- Recognize overlapping subproblems and optimal substructure — when DP applies at all.
- Contrast DP with greedy and plain divide-and-conquer.
- Turn a naive recursion into memoization (top-down) and tabulation (bottom-up).
- Follow a repeatable method to define a DP state and derive its recurrence.
- Solve climbing stairs, house robber, coin change and LIS with honest complexity.
- Reconstruct the optimal choice, not just its value.
1 · When does DP apply? advanced
DP needs two properties. Overlapping subproblems: a naive recursion solves the same smaller problem many times. Optimal substructure: an optimal solution is built from optimal solutions to subproblems. If both hold, cache the subproblem answers and the exponential blowup collapses to polynomial.
The clearest illustration is Fibonacci. Naive recursion recomputes fib(k) exponentially often; memoizing makes each of the n subproblems solved exactly once.
pythoncalls = {"naive": 0, "memo": 0}
def fib_naive(n):
calls["naive"] += 1
if n < 2:
return n
return fib_naive(n - 1) + fib_naive(n - 2) # recomputes the same n repeatedly
def fib_memo(n, cache={}):
calls["memo"] += 1
if n < 2:
return n
if n not in cache:
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
print("fib(30) =", fib_naive(30), "in", calls["naive"], "naive calls")
print("fib(30) =", fib_memo(30), "in", calls["memo"], "memoized calls")
fib(30) = 832040 in 2692537 naive calls
fib(30) = 832040 in 59 memoized calls| Paradigm | Subproblems | Reuse? | Choice rule |
|---|---|---|---|
| divide & conquer | disjoint (e.g. two halves) | no overlap | split & combine |
| dynamic programming | overlapping | cache & reuse | try all, keep best |
| greedy | one choice, no revisiting | n/a | locally best, commit |
2 · Memoization vs tabulation intermediate
There are two ways to fill the cache. Memoization (top-down) keeps the natural recursion and stores each answer the first time it is computed. Tabulation (bottom-up) throws away recursion and fills an array in dependency order. Same complexity; different trade-offs.
| Memoization (top-down) | Tabulation (bottom-up) | |
|---|---|---|
| writing | keep the recursion, add a cache | rewrite as an array fill |
| computes | only reachable states (lazy) | every state (eager) |
| risk | recursion-depth limit | wasted states if many unused |
| space | cache + call stack | table (often reducible) |
dp[i] and say in words what it means. (2) Transition — express dp[i] using strictly smaller states. (3) Base case — the smallest states you can fill directly. (4) Order — fill so every state's dependencies are ready. (5) Answer — which state (or aggregate) is the result. If you can write these five lines, the code is mechanical.3 · Climbing stairs — the smallest real DP intermediate
You climb n stairs taking 1 or 2 steps at a time; how many distinct ways? Apply the method. State: dp[i] = ways to reach step i. Transition: you arrive at i from i-1 (a 1-step) or i-2 (a 2-step), so dp[i]=dp[i-1]+dp[i-2]. Base: dp[0]=dp[1]=1. It is Fibonacci in disguise — Θ(n) time, and Θ(1) space once you keep only two values.
pythondef climb_table(n):
dp = [0] * (n + 1)
dp[0] = dp[1] = 1 # base cases
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # transition
return dp[n]
def climb_o1(n):
a, b = 1, 1 # only the last two states matter
for _ in range(2, n + 1):
a, b = b, a + b
return b
print([climb_table(n) for n in range(1, 9)])
print("space-O(1) agrees:", all(climb_table(n) == climb_o1(n) for n in range(1, 30)))
[1, 2, 3, 5, 8, 13, 21, 34]
space-O(1) agrees: True4 · House robber — a real choice per state advanced
Houses in a row hold cash; you cannot rob two adjacent houses. Maximize the loot. This introduces a genuine decision at each state. State: dp[i] = max loot considering houses 0..i. Transition: either skip house i (dp[i-1]) or rob it and add nums[i]+dp[i-2]; take the max. That 'skip vs take, keep the better' shape is the heart of most DP.
pythondef rob(nums):
if not nums:
return 0, []
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
take = nums[i] + (dp[i - 2] if i >= 2 else 0)
skip = dp[i - 1]
dp[i] = max(take, skip)
# reconstruct which houses were robbed
chosen, i = [], n - 1
while i >= 0:
take = nums[i] + (dp[i - 2] if i >= 2 else 0)
if take >= dp[i - 1] if i >= 1 else True:
if (dp[i] == take):
chosen.append(i); i -= 2
continue
i -= 1
return dp[-1], sorted(chosen)
loot, houses = rob([2, 7, 9, 3, 1])
print("max loot:", loot, "robbing house indices:", houses)
print("check no two adjacent:", all(houses[k+1]-houses[k] >= 2 for k in range(len(houses)-1)))
max loot: 12 robbing house indices: [0, 2, 4]
check no two adjacent: True5 · Coin change — minimization & unbounded choices advanced
Given coin denominations and an amount, find the fewest coins that sum to it (each coin usable unlimited times). State: dp[x] = min coins to make amount x. Transition: dp[x]=1+min(dp[x-c]) over coins c≤x. Base: dp[0]=0; unreachable amounts stay ∞. Complexity Θ(amount × #coins). This is where greedy fails — with coins {1,3,4} and amount 6, greedy takes 4+1+1=3 coins but the optimum is 3+3=2.
pythondef coin_change(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x and dp[x - c] + 1 < dp[x]:
dp[x] = dp[x - c] + 1
return dp[amount] if dp[amount] != INF else -1
def greedy(coins, amount):
count = 0
for c in sorted(coins, reverse=True):
while amount >= c:
amount -= c; count += 1
return count if amount == 0 else -1
coins = [1, 3, 4]
print("DP optimum for 6:", coin_change(coins, 6))
print("greedy for 6: ", greedy(coins, 6))
print("DP for 11 with [1,2,5]:", coin_change([1, 2, 5], 11))
DP optimum for 6: 2
greedy for 6: 3
DP for 11 with [1,2,5]: 36 · Longest increasing subsequence — two DP shapes expert
The LIS of a sequence is the longest subsequence whose values strictly increase. The natural DP is Θ(n²): dp[i] = length of the best increasing subsequence ending at i, transitioning from any earlier j with nums[j]<nums[i]. A cleverer version uses binary search on a 'tails' array for Θ(n log n) — the patience-sorting insight.
pythonfrom bisect import bisect_left
def lis_n2(nums):
if not nums:
return 0
dp = [1] * len(nums) # dp[i]=LIS ending at i
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
def lis_nlogn(nums):
tails = [] # tails[k]=smallest tail of an LIS of length k+1
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)
seq = [10, 9, 2, 5, 3, 7, 101, 18]
print("O(n^2) LIS:", lis_n2(seq), " O(n log n) LIS:", lis_nlogn(seq))
print("agree on random-ish input:",
lis_n2([3,1,4,1,5,9,2,6,5,3,5]) == lis_nlogn([3,1,4,1,5,9,2,6,5,3,5]))
O(n^2) LIS: 4 O(n log n) LIS: 4
agree on random-ish input: TrueΘ(n²) state is 'best ending at i'. The Θ(n log n) version keeps a monotone tails array where tails[k] is the smallest possible tail of an increasing subsequence of length k+1; binary search places each element. Reframing the state is often how you drop a complexity class.Checkpoint expert
✓ Checkpoint — you can move on when you can…
- Name the two properties a problem needs before DP is the right tool.
- Write the five-line method (state, transition, base, order, answer) for a new problem.
- Convert a naive recursion into both memoized and tabulated forms.
- Explain why coin change needs DP where standard-currency change can be greedy.
- State the LIS complexity for both the O(n²) and O(n log n) formulations.
A colleague solves 'min coins' greedily and it passes their tests with US coins, then fails in production with a custom loyalty-point denomination set. What happened?
Show answer
dp[x]=1+min(dp[x-c]) tries every coin and is correct for any denominations.In house robber, why is the transition dp[i]=max(dp[i-1], nums[i]+dp[i-2]) rather than nums[i]+dp[i-2]?
Show answer
i is optional. dp[i-1] is the best you can do if you skip i; nums[i]+dp[i-2] is the best if you rob it (which forbids i-1). Taking the max encodes the choice. Dropping dp[i-1] would force you to rob every other house even when skipping is better.🪜 Practice ladder beginner → industry
Six graded exercises, easy to real-world. Try each before opening its solution.
Context: A variant of climbing stairs where each step has a cost; used to teach that the 'answer state' is not always the last cell.
Your task: Given cost[i] to step on stair i, find the min cost to reach the top (past the last stair), starting from step 0 or 1.
Requirements:
- Transition: dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
- The top is one past the last index — answer is min(dp[n-1], dp[n-2]).
- Return the numeric minimum cost.
💡 Hint: Fill dp left to right; the top can be reached from either of the last two stairs.
Show solution
pythondef min_cost_climb(cost):
n = len(cost)
dp = [0] * n
dp[0], dp[1] = cost[0], cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
return min(dp[-1], dp[-2]) # top is beyond the last stair
print(min_cost_climb([10, 15, 20])) # 15
print(min_cost_climb([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6
15
6Context: Unlike min-coins, here we count the number of distinct combinations that sum to an amount — the classic 'combinations not permutations' DP subtlety.
Your task: Given coin denominations and an amount, count how many distinct coin combinations sum to it (order does not matter).
Requirements:
- Loop coins on the OUTSIDE and amount on the inside to avoid counting permutations.
- dp[0] = 1 (one way to make 0: use nothing).
- Return dp[amount].
💡 Hint: Iterating coins outermost means each combination is counted once, in a fixed coin order.
Show solution
pythondef count_change(coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins: # coins OUTSIDE => combinations, not permutations
for x in range(c, amount + 1):
dp[x] += dp[x - c]
return dp[amount]
print(count_change([1, 2, 5], 5)) # 4: 5, 2+2+1, 2+1+1+1, 1*5
print(count_change([2], 3)) # 0
print(count_change([1, 5, 10, 25], 100)) # 242
4
0
242Context: Word break (can a string be segmented into dictionary words?) powers tokenizers and spell-correctors; it is a 1-D boolean DP over string prefixes.
Your task: Given a string and a word dictionary, return True if the string can be split into a sequence of dictionary words.
Requirements:
- State: dp[i] = can s[:i] be segmented.
- Transition: dp[i] is True if some j
- dp[0] = True (empty prefix).
💡 Hint: For each end index i, scan split points j and check dp[j] and the substring s[j:i].
Show solution
pythondef word_break(s, words):
wordset = set(words)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # empty prefix is segmentable
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in wordset:
dp[i] = True
break
return dp[n]
print(word_break("leetcode", ["leet", "code"])) # True
print(word_break("applepenapple", ["apple", "pen"])) # True
print(word_break("catsandog", ["cats","dog","sand","and","cat"])) # False
True
True
FalseContext: Decoding a digit string into letters (A=1..Z=26) is the DP that trips people on the edge cases: leading zeros and the 10/20 specials.
Your task: Count how many ways a digit string decodes to letters, where 1..26 map to A..Z.
Requirements:
- State: dp[i] = ways to decode s[:i].
- One-digit step valid if s[i-1] != '0'; two-digit step valid if s[i-2:i] in 10..26.
- Return dp[n]; handle strings that cannot decode (return 0).
💡 Hint: At each position add dp[i-1] if the single digit is 1-9 and dp[i-2] if the pair is 10-26.
Show solution
pythondef num_decodings(s):
if not s or s[0] == "0":
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
if s[i - 1] != "0": # single digit 1-9
dp[i] += dp[i - 1]
if "10" <= s[i - 2:i] <= "26": # pair 10-26
dp[i] += dp[i - 2]
return dp[n]
print(num_decodings("12")) # 2 -> "AB","L"
print(num_decodings("226")) # 3 -> "BZ","VF","BBF"
print(num_decodings("06")) # 0 -> leading zero
2
3
0Context: Max-product subarray is a favorite because a single running max fails: a negative times a negative flips to a large positive, so you must track the running MIN too.
Your task: Find the largest product of any contiguous subarray (may contain negatives and zeros).
Requirements:
- Track both the current max and current min product ending here.
- On a negative number, swap max/min before updating.
- Return the best max seen; verify against brute force.
💡 Hint: hi = max(x, hi*x, lo*x); lo = min(x, hi_old*x, lo*x) — the min can become the new max after a sign flip.
Show solution
pythondef max_product(nums):
best = hi = lo = nums[0]
for x in nums[1:]:
if x < 0:
hi, lo = lo, hi # sign flip swaps roles
hi = max(x, hi * x)
lo = min(x, lo * x)
best = max(best, hi)
return best
def brute(nums):
b = nums[0]
for i in range(len(nums)):
prod = 1
for j in range(i, len(nums)):
prod *= nums[j]; b = max(b, prod)
return b
for t in ([2,3,-2,4], [-2,0,-1], [-2,3,-4], [2,-5,-2,-4,3]):
print(t, "->", max_product(t), "brute:", brute(t))
[2, 3, -2, 4] -> 6 brute: 6
[-2, 0, -1] -> 0 brute: 0
[-2, 3, -4] -> 24 brute: 24
[2, -5, -2, -4, 3] -> 24 brute: 24Context: A state-machine DP straight out of quant/fintech interviews: after selling you must cool down one day before buying again. It teaches modeling a DP as explicit states.
Your task: Given daily prices, maximize profit with unlimited transactions, but you cannot buy on the day right after you sell (one-day cooldown).
Requirements:
- Model three states per day: hold (own a share), sold (just sold today), rest (idle, free to buy).
- Transitions: hold = max(hold, rest - price); sold = hold + price; rest = max(rest, sold).
- Answer is max(sold, rest) on the last day; verify on a known example.
💡 Hint: Track the three running values across days; 'rest' after a 'sold' enforces the cooldown because you can only buy from 'rest'.
Show solution
pythondef max_profit_cooldown(prices):
if not prices:
return 0
hold = float("-inf") # best profit while holding a share
sold = 0 # best profit having just sold today
rest = 0 # best profit resting (not holding, free to buy)
for price in prices:
prev_sold = sold
sold = hold + price # sell today
hold = max(hold, rest - price) # keep holding, or buy from a rest day
rest = max(rest, prev_sold) # rest; can absorb yesterday's sale (cooldown)
return max(sold, rest)
print(max_profit_cooldown([1, 2, 3, 0, 2])) # 3: buy1 sell3, cooldown, buy0 sell2
print(max_profit_cooldown([1])) # 0
print(max_profit_cooldown([6, 1, 3, 2, 4, 7]))# 6
3
0
6