Solving optimization problems by breaking them into overlapping subproblems.
Solving optimization problems by breaking them into overlapping subproblems.
Naive recursive Fibonacci is a machine for re-answering questions. Ask it for fib(50) and it computes fib(20) from scratch 1,346,269 separate times, getting the same answer at every single one. Backtracking has the same blind spot: it happily re-explores states it has already settled. Dynamic programming is the fix, and it's really just recursion that writes its answers down: solve each distinct subproblem once, store the result, and look it up every time the question repeats.
Two conditions make a problem worth the notebook. Richard Bellman named the technique in the 1950s, and his recipe needs overlapping subproblems (the same questions come back, so caching pays) and optimal substructure (the best answer to the whole is built from best answers to the parts). When each answer builds on a handful of previous ones, exponential problems collapse into a single pass down an array. That array is the "1D" in the title.
Count the waste before fixing it. Naive fib(10) makes exactly 177 calls, because both branches re-derive everything below them. Predict before reading on: how many calls does fib(11) make, one step up?
The answer is 287, nearly double, because the call count grows at about 1.6ⁿ, the golden ratio that runs the Fibonacci sequence itself. Now add a dictionary. Only 11 distinct subproblems exist between fib(0) and fib(10), so the memoized version computes each once and answers the other 166 calls from the notes. One argument-keyed cache turns an exponential tree into a straight line of O(n) work.
Memoization starts at the top and recurses down. Tabulation flips the direction: start from the base cases and fill an array forward until the answer falls out the far end, no recursion anywhere. The classic vehicle is House Robber: houses hold loot, adjacent houses can't both be robbed, maximize the haul. Define dp[i] as the best loot using houses 0 through i, and each house offers one choice: skip it and keep dp[i - 1], or rob it and add dp[i - 2].
Trace it on [2, 7, 9, 3, 1]. The bases are dp[0] = 2 and dp[1] = 7. House 2 compares skipping (7) against robbing (2 + 9 = 11) and takes 11. House 3 compares 11 against 7 + 3 = 10 and keeps 11. House 4 compares 11 against 11 + 1 = 12, and the final cell reads 12: rob houses 0, 2, and 4.
The picture to keep is a spreadsheet where every cell looks at one or two earlier cells. Just know what the picture leaves out: the spreadsheet shows the fill order, not where the formula came from. Deriving the recurrence is the actual work, and it always comes from listing the choices.
You might think dynamic programming is the cache, since "recursion plus memoization" is how everyone first meets it. The cache is the easy half. The skill that transfers between problems is deciding what dp[i] means, because that one sentence dictates the recurrence, the base cases, and where the final answer lives. Climbing Stairs reads "ways to reach step i", Coin Change reads "fewest coins for amount i", Word Break reads "whether the first i characters can be segmented". Same machinery, completely different sentences.
Sometimes the honest state needs more than one number. Maximum Product Subarray tracks both the largest and the smallest product ending at each index, because one negative factor turns the current minimum into the next maximum. When a single-value state keeps producing wrong answers, the state is usually missing a dimension, not the recurrence.
The code above shows the last refinement: Climbing Stairs only ever reads the previous two cells, so the array collapses into two rolling variables and the space cost drops from O(n) to O(1). Fibonacci and House Robber collapse the same way.
dp[i] is the ..." in plain words before writing any code. Best loot using houses 0 through i, number of ways to reach step i, fewest coins for amount i. A fuzzy state guarantees a wrong recurrence.i or robbed it, so dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]). Every recurrence is a list of last moves with the best one kept.dp[0], dp[1]), then fill forward so every cell's dependencies are ready before the cell itself. Sizing the array n + 1 gives the empty case a home at index 0.dp[i] only reads a fixed number of earlier cells, the whole array collapses into that many variables. Do it after the table version works, never before.Most 1D problems are one of three shapes. Fixed lookback, where dp[i] reads a constant number of earlier cells (Climbing Stairs, House Robber). Full scans, where each state tries every option (Coin Change tries every coin per amount, Longest Increasing Subsequence checks every earlier index, which is O(n²) until the patience-sorting trick brings it to O(n log n)). And knapsacks, where the array is indexed by a budget instead of a position (Partition Equal Subset Sum).
The boundary worth knowing cold is the one with greedy. Hand a greedy coin counter the coins [1, 3, 4] and the amount 6, and it takes the 4, then a 1, then another 1: three coins. The table finds 3 + 3: two. Greedy commits to the biggest coin and never looks back, while dynamic programming weighs every coin at every amount, which is exactly the difference between the two techniques. When a local rule can be proven safe, greedy wins on simplicity. When it can't, the table is the insurance.
The recurrences differ per problem, but the working habits carry straight across. Five worth keeping:
5% faster.Quiz yourself before starting: what exactly does dp[i] mean in House Robber, and why does Longest Increasing Subsequence return max(dp) instead of the last cell? Nail those two and the problems below become exercises in writing the state sentence. Start with the Fibonacci-shaped ones, then the choice scans, then the knapsacks:
Completed | Title | Status | Notes | Solution | |
|---|---|---|---|---|---|
memoized_fibonacci.py
def fib(n: int, memo: dict[int, int] | None = None) -> int:
if memo is None:
memo = {}
# Base cases end the recursion
if n < 2:
return n
# Answered before: return the note instead of recomputing
if n in memo:
return memo[n]
# Solve once, write it down, reuse forever
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]house_robber.py
def rob(nums: list[int]) -> int:
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
# dp[i] holds the best loot using houses 0 through i
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
# Choice: skip house i, or rob it plus the best two back
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
# The state is "up to i", so the answer is the last cell
return dp[n - 1]climbing_stairs_(two_variables).py
def climb_stairs(n: int) -> int:
# Ways to stand on the previous two steps
prev, current = 1, 1
for _ in range(2, n + 1):
# Each step is reached from one or two below
prev, current = current, prev + current
return current