Drag across the ledger. Click it, then use ← → to step and Space to play.
Dynamic programming is recursion whose subproblems overlap, solved once each. Plain recursion for climb_stairs(5) asks for climb_stairs(3) twice, climb_stairs(2) three times, and so on: an exponential pile of repeats (the call tree on page 3). DP turns it around: bottom-up, it fills a ledger from the smallest case up, so every answer it needs is already written down. And since each entry only reads the last one or two entries (or the row above), the rest can be forgotten: often just the last two values or the last row are kept.
FIG. 11 · A ledger of answers, filled in order. Red is the entry being computed; red-ringed entries are the ones it reads, with arrows showing the dependency. Hatched entries are base cases. Faded entries have been forgotten, because nothing will read them again; the black tags (one, two, row, new, rob1, rob2) are the only values the code still holds.
def climb_stairs(n): # 1-D: ways(n) = ways(n-1) + ways(n-2)
one, two = 1, 1 # keep only the last two answers
for _ in range(n - 1):
one, two = one + two, one
return one
def unique_paths(m, n): # 2-D: dp[r][c] = up + left
row = [1] * n
for _ in range(m - 1):
new = [1] * n
for c in range(1, n):
new[c] = new[c - 1] + row[c]
row = new
return row[-1]
def rob(nums): # LeetCode 198
rob1, rob2 = 0, 0 # best up to two houses back, one back
for x in nums:
rob1, rob2 = rob2, max(rob1 + x, rob2) # rob x, or skip it
return rob2
def longestCommonSubsequence(a, b): # LeetCode 1143
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 # match: diagonal + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
houses = [2, 7, 9, 3, 1], and you can't rob two neighbours. At each house: rob it plus the best from two back, or skip it and keep the best from one back. Two running numbers are enough. Answer: 12 (2 + 9 + 1). Trigger: "maximum", choices that repeat subproblems.
a = "abcde", b = "ace". dp[i][j] is the LCS of the first i letters of a and first j of b. Matching letters extend the diagonal; otherwise take the better of dropping one letter. Answer: 3 ("ace"). Trigger: "longest common subsequence".
| Shape | Time | Space | Why |
|---|---|---|---|
| 1-D (climb stairs, house robber) | O(n) | O(1) with two variables | One entry per position, each reading the previous one or two. Older entries are never read again. |
| 2-D grid (unique paths) | O(m × n) | O(n) with one row | One entry per cell, each reading up and left. Rows above the previous one are never read again. |
| 2-D strings (LCS) | O(m × n) | O(m × n) full table, O(n) for length only | Keep the whole table if you need to trace back the actual subsequence. |
| Plain recursion, no memo | O(2ⁿ) | O(n) stack | Every call branches and the branches overlap, so the same subproblem is solved again and again. |
Top-down is the recursion plus a memo dict (page 3): it only solves the subproblems it actually reaches, and reads like the recurrence. Bottom-up is a loop that fills the table from the base cases: no recursion depth limit, and once you see which entries each step reads, you can shrink the table to the last row or the last two values. Same answers, same O(time); bottom-up usually wins on space.
Ask: what is the last choice? For stairs, the last move was 1 or 2 steps. For a grid, the robot arrived from above or from the left. For houses, the last house was robbed or skipped. Each option leaves a smaller version of the same problem, and the answer combines them with +, min or max.
Combine the answers of smaller cases with +, min, max or or.
A 2-D table indexed by a prefix of each.
The tell is choices that repeat subproblems: if the recursion tree would ask the same question twice, store the answer.
def climb_stairs(n): # 1-D: ways(n) = ways(n-1) + ways(n-2)
one, two = 1, 1 # keep only the last two answers
for _ in range(n - 1):
one, two = one + two, one
return one
def unique_paths(m, n): # 2-D: dp[r][c] = up + left
row = [1] * n
for _ in range(m - 1):
new = [1] * n
for c in range(1, n):
new[c] = new[c - 1] + row[c]
row = new
return row[-1]