Climbing Stairs and 1-D DP
DSA · Dynamic Programming
Theory
One-dimensional DP problems have a state that depends on a single index, such as "the number of ways to reach step i" or "the best amount robbed up to house i". Each answer is computed from a few previous answers, so only the last few values need to be kept, reducing space to O(1). Climbing stairs (1 or 2 steps) follows ways(i) = ways(i-1) + ways(i-2); house robber follows best(i) = max(best(i-1), best(i-2) + value[i]).
Why we use it
1-D DP patterns appear in many interview problems and show how to turn a recurrence into a fast loop.
When to use it
Use it for counting paths with step choices, maximising non-adjacent picks, decoding messages, minimum cost to reach the end, and similar linear problems.
How it works
- ways[0] = 1, ways[1] = 1
- For i = 2..n
- ways[i] = ways[i-1] + ways[i-2]
- Return ways[n]
Syntax
ways[0] = ways[1] = 1
ways[i] = ways[i-1] + ways[i-2]
best[i] = max(best[i-1], best[i-2] + v[i])
Time: O(n) Space: O(1) with two variablesExample
def climb(n):
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a
def house_robber(values):
prev, cur = 0, 0
for v in values:
prev, cur = cur, max(cur, prev + v)
return cur
def min_cost_stairs(cost):
a = b = 0
for c in cost:
a, b = b, min(a, b) + c
return min(a, b)
print("Ways to climb 10 stairs:", climb(10))
print("Best robbery from [2,7,9,3,1]:", house_robber([2, 7, 9, 3, 1]))
print("Min cost stairs:", min_cost_stairs([10, 15, 20]))Key points
- State depends on one index
- Each answer uses a few previous answers
- Space can often be O(1)
- Write the recurrence before coding