#70
Climbing Stairs
Easy 1D DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
You climb a staircase of n steps, taking 1 or 2 steps at a time. Count the distinct ways to reach the top.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: ways to climb n steps taking 1 or 2 at a time.
Why this works: your last move came from step n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2).
Example: n = 4
ways: 1, 1, 2, 3, 5 → 5✦Hints open one at a time
To stand on step i, your last move came from step i − 1 or step i − 2.
ways(i) = ways(i − 1) + ways(i − 2) — Fibonacci again.
↗Approach
Define the state (ways to reach step i), the transition (sum of the two previous) and the base cases (ways(0) = ways(1) = 1). Only the last two values are needed.
</>Solution (Java)
class Solution {
public int climbStairs(int n) {
int prev = 1, cur = 1; // ways(0), ways(1)
for (int i = 2; i <= n; i++) {
int next = prev + cur;
prev = cur;
cur = next;
}
return cur;
}
}!Common mistake
Plain recursion without memoisation — exponential time.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon