Climbing Stairs
Medium · rating 1050 · dp
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).