Climbing Stairs
Medium · rating 1050 · Dynamic Programming
You are climbing a staircase of n steps, taking either 1 or 2 steps at a time. Print how many distinct ways there are to reach the top.
Constraints: 1 ≤ n ≤ 45
Editorial
Approach
To reach step n your last move was either a single step (from n−1) or a double step (from n−2). So the number of ways satisfies ways(n) = ways(n−1) + ways(n−2) — the Fibonacci recurrence.
From recursion to O(1) space
Naïve recursion recomputes the same subproblems exponentially. Since each value only needs the previous two, we can iterate upward keeping just two running totals instead of a full table.
a, b = 1, 1 # ways(0), ways(1)
for _ in range(n):
a, b = b, a + b
return aComplexity
Time: O(n). Space: O(1).
Related problems
- Best Time to Buy and Sell Stock — Easy
- Nth Fibonacci — Medium
- Maximum Subarray Sum — Medium
- Dice Sum Ways — Medium
- House Robber — Hard
- Unique Grid Paths — Hard