Dynamic Programming7 min read

1D DP

Build the answer one step at a time — just like climbing stairs
time:Linear · \(O(n)\)space:\(O(n)\) or \(O(1)\) optimized

Imagine you're climbing a staircase. To reach step 10, you had to come from either step 9 (one step up) or step 8 (two steps up). There's no other way. That simple observation is the heart of 1D Dynamic Programming.

Instead of trying every possible path from scratch each time, DP says: "I already figured out the best way to reach step 8 and step 9 — so step 10 is trivial." We build up the answer piece by piece, reusing what we already know.

The Gateway: Fibonacci

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, …) is defined as F(n) = F(n-1) + F(n-2). A naive recursive approach recalculates F(3) over and over again deep inside F(5), F(6), F(7)… it snowballs into \(O(2^n)\) work.

DP's fix is simple: compute F(0), F(1), F(2), … in order and store each result. Each value takes one addition. Total: \(O(n)\). And if you only need the last two values, you can keep just two variables instead of the whole array — \(O(1)\) space.

Climbing Stairs

You can take 1 or 2 steps at a time. How many different ways can you reach step n? At every step i, you came from step i-1 or step i-2, so: dp[i] = dp[i-1] + dp[i-2]. Base cases: dp[1] = 1, dp[2] = 2. This is exactly Fibonacci, just offset by one.

House Robber

Given a row of houses with dollar amounts inside, you can't rob two houses next to each other. Maximize the total haul. At house i you make a choice: skip it (best you had at house i-1) or rob it (what you had two houses ago plus this house's cash). Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

The Rolling-Variable Trick

Whenever dp[i] only looks back a fixed number of steps (like the last 2), you don't need the whole array. Keep just those few variables, update them at each step, and your space drops from \(O(n)\) to \(O(1)\). This trick works for Fibonacci, climbing stairs, house robber, and countless other 1D DP problems.

Note: DP doesn't find a clever shortcut — it avoids repeating work. Every subproblem is solved exactly once, then remembered. That's it.

House Robber — DP with rolling variables

def rob(nums):
    prev2, prev1 = 0, 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1


print(rob([2, 7, 9, 3, 1]))   # 12
print(rob([1, 2, 3, 1]))      # 4
Output
12
4

Complexity

🐌 Naive Fibonacci recursionSame subproblems recomputed over and over — grows like a binary tree
Exponential\(O(2^n)\)
⚡ 1D DP (time)Each of the n states is computed exactly once
Linear\(O(n)\)
📦 1D DP (space, full array)Store all n states — useful if you need to reconstruct the path
Linear storage\(O(n)\)
🪄 1D DP (rolling variables)When dp[i] depends on only the last k states — keep just those k variables
Constant storage\(O(1)\)
🏠 House Robber circular variantCan't rob house 0 and house n-1 together — run robber on [0..n-2] and [1..n-1], take the max
Two linear passes\(O(n)\)

Quick check

How many ways can you reach step 5 in the climbing stairs problem (1 or 2 steps at a time)?

Continue reading

DP Pattern
Never solve the same puzzle piece twice — write it down and look it up next time
→
Memoization vs Tabulation
Top-down is calling a friend who calls a friend. Bottom-up is filling a spreadsheet row by row.
→
0/1 Knapsack
Pack a suitcase for maximum value — each item is all-or-nothing
→