-
Notifications
You must be signed in to change notification settings - Fork 0
026 — 1D Dynamic Programming
Picture climbing a staircase where, at every step, you're allowed to take either one stair or two. If someone asks "how many distinct ways are there to reach step 10?", you could try to enumerate every possible sequence of 1s and 2s — but there's a shortcut hiding in plain sight: the number of ways to reach step 10 is just the number of ways to reach step 9 (then take one more stair) plus the number of ways to reach step 8 (then take a two-stair hop). And the number of ways to reach step 9 is, by the same logic, built from steps 8 and 7. You never need to re-derive the whole staircase from scratch for each step — you just remember the answer for every step you've already solved and combine a small, fixed number of those remembered answers to get the next one. That's 1-D dynamic programming: today's answer is a simple combination of a few of yesterday's answers, and you walk forward remembering just enough of the past to build the present.
Reach for 1-D DP when you see:
- "Number of distinct ways to..." — reach a target, make change, climb stairs, decode a string — counting problems where each choice branches into a few sub-choices that combine additively.
-
"Minimum/maximum cost to reach..." — minimum cost climbing stairs, minimum coins to make an amount — optimization problems where the cost to reach state
idepends only on the costs to reach a few nearby earlier states. -
A recurrence that only looks back a fixed, small number of steps — "each step's answer depends only on the previous one or two answers" (a Fibonacci-shaped recurrence) is the strongest possible tell; if you can write
dp[i] = f(dp[i-1], dp[i-2], ...)for some fixed small window, it's 1-D DP. - "House Robber"-style constraints: "you can't pick two adjacent items," "maximize the sum subject to a no-two-consecutive rule" — the decision at each index is binary (take it or don't), and the state needed to make that decision collapses to just "what happened right before."
The unifying tell: the array/sequence has a single linear axis you sweep along, and each position's answer is built from a small, fixed number of previous positions' answers — not from the whole history, and not from two independent sequences being compared (that's 2-D DP).
Filling a 1-D dp array left to right, where each cell only looks back at the one or two cells right behind it:
Climbing Stairs — dp[i] = number of ways to reach step i
dp[i] = dp[i-1] + dp[i-2]
step: 0 1 2 3 4 5
dp: [ 1, 1, 2, 3, 5, 8]
^ ^
| |
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
each cell only ever reaches back TWO cells — never further
func oneDimensionalDPTemplate(_ n: Int) -> Int {
guard n > 0 else { return 0 } // 🔧 Fill in: handle the actual base case(s)
var dp = Array(repeating: 0, count: n + 1)
dp[0] = 1 // 🔧 Fill in: base case for position 0 (or 1, depending on indexing)
if n >= 1 { dp[1] = 1 } // 🔧 Fill in: base case for position 1, if the recurrence needs two anchors
for i in 2...n {
dp[i] = dp[i - 1] + dp[i - 2] // 🔧 Fill in: the actual recurrence — combine a FIXED
// small number of earlier states, not the whole array
}
return dp[n] // 🔧 Fill in: return the final answer, or track it as you go for "min/max" variants
}
// Space-optimized shape: since the recurrence only ever looks back a fixed
// window (here, 2 states), you rarely need the whole dp array in memory —
// two rolling variables are enough.
func oneDimensionalDPRolling(_ n: Int) -> Int {
guard n > 1 else { return 1 } // 🔧 Fill in: adjust base cases to match the problem
var prev2 = 1 // dp[i-2]
var prev1 = 1 // dp[i-1]
for _ in 2...n {
let current = prev1 + prev2 // 🔧 Fill in: the actual recurrence
prev2 = prev1
prev1 = current
}
return prev1
}House Robber — given an array nums representing money stashed in houses along a street, return the maximum amount you can rob without robbing two adjacent houses.
func rob(_ nums: [Int]) -> Int {
guard !nums.isEmpty else { return 0 }
guard nums.count > 1 else { return nums[0] }
var prev2 = 0 // best amount robbing up through house i-2 (0 houses back = 0)
var prev1 = nums[0] // best amount robbing up through house i-1
for i in 1..<nums.count {
// At house i: either skip it (keep prev1's best), or rob it
// (nums[i] plus the best from two houses back, since i-1 is now off-limits).
let current = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = current
}
return prev1
}
// smoke test
print(rob([1, 2, 3, 1])) // 4 (rob house 0 and house 2: 1 + 3)
print(rob([2, 7, 9, 3, 1])) // 12 (rob houses 0, 2, 4: 2 + 9 + 1)
print(rob([2, 1, 1, 2])) // 4 (rob houses 0 and 3: 2 + 2)
print(rob([5])) // 5This maps directly onto the rolling template: dp[i] represents "the max take considering houses 0...i," and the recurrence is exactly a two-state lookback — dp[i] = max(dp[i-1], dp[i-2] + nums[i]), i.e., either skip house i (inherit dp[i-1]) or rob it (take nums[i] plus whatever was best two houses back, since house i-1 becomes forbidden the moment you rob house i). Only prev1 and prev2 are ever needed, so the full dp array collapses to two rolling variables.
1-D DP is the staircase — each step's answer is just a small, fixed combination of the answers to a couple of steps right behind it, remembered instead of recomputed.
"Coin Change" (minimum number of coins to make amount n, given unlimited coins of given denominations) also fits the 1-D DP shape — dp[i] depends on earlier dp values. But unlike House Robber's fixed two-state lookback, how many earlier states does dp[i] depend on here, and what determines that number?
⬅️ Previous: Top-K and Heap Pattern · Next: 2D Dynamic Programming ➡️