What you will learn
- A four-step recipe for any DP problem.
- 1D DP with O(1) space, and when 2D tables are needed.
- Top-down memoisation versus bottom-up tables.
Signals
- “Number of ways”, “minimum/maximum cost”, “longest/shortest”, “is it possible”.
- Choices at each step, where brute force recursion recomputes the same subproblems.
- Greedy looks tempting but has counterexamples.
The recipe
- State: what does
dp[i](ordp[i][j]) mean, in words? - Recurrence: how is it built from smaller states?
- Base cases: the smallest states you know directly.
- Order and answer: fill in an order where dependencies are ready; say which cell holds the answer.
Writing step 1 as a sentence (“dp[a] = fewest coins that make amount a”) is the most valuable habit in DP.
Code
"""Dynamic programming: 1D (climbing stairs, house robber, coin change, LIS) and 2D (LCS, edit distance)."""
from bisect import bisect_left
from functools import lru_cache
def climb_stairs(n):
a, b = 1, 1 # ways to reach step i-1 and step i
for _ in range(n - 1):
a, b = b, a + b
return b
def rob(houses):
take, skip = 0, 0 # best total if we rob / don't rob the previous house
for h in houses:
take, skip = skip + h, max(take, skip)
return max(take, skip)
def coin_change(coins, amount):
INF = amount + 1
dp = [0] + [INF] * amount # dp[a] = fewest coins for amount a
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return -1 if dp[amount] == INF else dp[amount]
def lis_length(nums):
tails = [] # tails[k] = smallest tail of an increasing subsequence 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)
def lcs(a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
def edit_distance(a, b):
@lru_cache(maxsize=None) # top-down memoisation of the same recurrence
def go(i, j):
if i == len(a):
return len(b) - j
if j == len(b):
return len(a) - i
if a[i] == b[j]:
return go(i + 1, j + 1)
return 1 + min(go(i + 1, j), # delete a[i]
go(i, j + 1), # insert b[j]
go(i + 1, j + 1)) # replace
return go(0, 0)
if __name__ == "__main__":
print([climb_stairs(n) for n in range(1, 8)])
print(rob([2, 7, 9, 3, 1]), coin_change([1, 2, 5], 11), coin_change([2], 3))
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))
print(lcs("abcde", "ace"), edit_distance("horse", "ros"), edit_distance("intention", "execution"))
Output:
[1, 2, 3, 5, 8, 13, 21]
12 3 -1
4
3 3 5
- Climbing stairs: ways(n) = ways(n−1) + ways(n−2). Only the last two values are needed, so O(1) space.
- House robber: for each house, either rob it (previous house skipped) or skip it. Two variables replace the table. Best for
[2, 7, 9, 3, 1]is 2 + 9 + 1 = 12. - Coin change:
dp[a] = 1 + min(dp[a − c]). Greedy fails for some coin sets; DP doesn’t. Amount 11 with 5 needs 3 coins; 3 with 2 is impossible. - Longest increasing subsequence: the O(n²) DP is
dp[i] = 1 + max(dp[j])over smaller earlier values; the code shows the O(n log n) “tails + binary search” version. - LCS (2D):
dp[i][j]= LCS of the first i characters of a and first j of b. Match → diagonal + 1; otherwise the max of dropping one character. - Edit distance (top-down): the same kind of 2D recurrence written as a memoised recursion: delete, insert or replace when characters differ.
Top-down or bottom-up?
- Top-down (recursion +
lru_cache): closest to the recurrence, computes only states you need. Watch recursion depth. - Bottom-up (tables): no recursion limit, easy space optimisation (keep only the previous row).
Start top-down to get it right, then convert if needed.
DP families worth recognising
| Family | Examples |
|---|---|
| Linear (1D) | Stairs, house robber, decode ways, word break |
| Knapsack | Coin change, partition equal subset sum, target sum |
| Subsequence | LIS, LCS, edit distance, distinct subsequences |
| Grid | Unique paths, minimum path sum |
| Interval | Burst balloons, palindrome partitioning |
| Bitmask | Travelling salesman for small n |
Practise: 1D DP, 2D DP and bitmask DP problems. For full problem lists, work through the Blind 75, LeetCode 150 and the DSA master sheet, naming the pattern before you code each one.
Key takeaways
- Define the state in words first, then the recurrence, base cases and fill order.
- Reduce space when each state depends only on a few previous ones.
- Memoised recursion and bottom-up tables are the same DP; pick what’s clearer, then optimise.
- Learn the families (knapsack, subsequence, grid, interval) to spot DP quickly.
Exercises
- Word break: can a string be split into dictionary words?
- Partition equal subset sum with a 1D boolean knapsack array.
- Rewrite
edit_distancebottom-up with only two rows of memory.
Quiz
- What is the state in coin change, in words?
- Why can house robber use two variables instead of an array?
- In LCS, what happens when
a[i-1] == b[j-1]?
Show answers
dp[a]is the fewest coins that add up to amount a (or infinity if impossible).- Each state depends only on the previous one or two states, so older values are never needed again.
- Both characters extend a common subsequence:
dp[i][j] = dp[i-1][j-1] + 1.