LeetCode 70 · 1-D DP · concept: dynamic-programming
Problem
You climb n stairs, 1 or 2 steps at a time. How many distinct ways to reach the top?
n = 3 -> 3 (1+1+1, 1+2, 2+1)
The recurrence — it’s Fibonacci
To reach stair i, your last move came from stair i−1 (a 1-step) or i−2 (a 2-step). So ways(i) = ways(i−1) + ways(i−2) — the Fibonacci recurrence.
Approach — bottom-up with two variables (optimal)
Only the last two results matter, so O(1) space.
def climbStairs(n):
prev, curr = 1, 1 # ways(0)=1, ways(1)=1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr # ways(i) = ways(i-1) + ways(i-2)
return currTime O(n), space O(1). Naive recursion is O(2ⁿ) — the same overlapping-subproblem blowup DP exists to kill.
Key insight
Count paths where each step depends on a fixed number of previous states → a Fibonacci-style DP. The whole skill is finding the recurrence (“the last move came from i−1 or i−2”); recognizing that many differently-worded problems share this exact recurrence is most of 1-D DP. The gateway problem for the category.
Related
- concept: dynamic-programming
- next: Min Cost Climbing Stairs
Software engineering
Infrastructure & security
Computer science
Hardware & engineering