1-D Dynamic Programming
Best answer here = best of a few earlier answers.
- Brute force
- O(2ⁿ) — plain recursion recomputes overlapping subproblems
- With the pattern
- O(n) — each state computed once (O(n·k) with k choices per state)
- Extra space
- O(1) with rolling variables, O(n) with a table
In plain English
“A burglar walks down a street of houses, but robbing two neighbours sets off the alarm. At each house they only need to ask: "is it better to rob this house plus my best haul from two doors back, or skip it and keep my best haul from the last house?" A sticky note with those two numbers is all they carry.”
Why it's fast
Plain recursion re-solves the same suffix/prefix exponentially many times (rob(i) gets called from i+1 and i+2, and so on). DP stores each subproblem's answer once: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). That's n subproblems × O(1) work = O(n), and since you only look back two steps, the table shrinks to two variables.
Spot it when the problem says…
- maximum / minimum total with a restriction
- number of ways to reach / decode
- cannot pick adjacent elements
- climbing stairs, 1 or 2 steps
- fewest coins to make amount
- can the string be segmented
Visualize
House robber — take it or skip it
Maximize loot from a row of houses without robbing two neighbours.
houses
dp[i] = best loot using the first i houses
dp[0] = 0: with no houses, there's nothing to take.
1def rob(houses):2 n = len(houses)3 dp = [0] * (n + 1) # dp[i] = best from first i houses4 dp[1] = houses[0]5 for i in range(2, n + 1):6 skip = dp[i - 1] # leave house i-17 take = dp[i - 2] + houses[i - 1] # rob it, skip its neighbour8 dp[i] = max(skip, take)9 return dp[n]How to apply it
- 01Define
dp[i]in one sentence (e.g. 'max money from the first i houses'). - 02Write the recurrence from the last decision: take vs skip, or which coin/step was used last.
- 03Set base cases (
dp[0],dp[1]) carefully. - 04Fill in order so dependencies are ready; return the right cell.
- 05If
dp[i]only needs a few previous cells, roll them into variables.
Variations you'll meet
Take vs skip (House Robber)
The visualizer's example.
def rob(nums: list[int]) -> int: prev2 = prev1 = 0 # best up to i-2, i-1 for x in nums: take = prev2 + x skip = prev1 prev2, prev1 = prev1, max(take, skip) return prev1Unbounded choices (Coin Change)
dp[a] = 1 + min(dp[a - c]) over coins; initialize to infinity, dp[0] = 0.
def coin_change(coins: list[int], amount: int) -> int: INF = amount + 1 dp = [0] + [INF] * amount for a in range(1, amount + 1): for c in coins: if c <= a: dp[a] = min(dp[a], dp[a - c] + 1) return dp[amount] if dp[amount] != INF else -1Top-down memo
Write the recursion, add @functools.cache. Fastest way to a correct answer in an interview; convert to bottom-up if asked.
Look-back over all j < i (LIS, Word Break)
dp[i] depends on every earlier dp[j], giving O(n²); LIS has an O(n log n) patience-sorting upgrade.
Common mistakes
- Not defining what
dp[i]means before coding, then mixing 'up to i' and 'ending at i'. - Wrong base cases (e.g. Decode Ways with a leading '0').
- Updating rolling variables in the wrong order and overwriting a value you still need.
- Initializing a min-DP with 0 instead of infinity.
- House Robber II: forgetting the first and last houses are adjacent — run twice excluding each end.
Practice ladder
Easy → hard. Tick them off as you go.
Think you've got it?
Let the AI interviewer throw a 1-D Dynamic Programming problem at you and grade how you explain it.