You're climbing a staircase with n steps. Each move you can go up 1 or 2 steps. Return how many distinct ways there are to reach the top.
Example
Input n = 3
Output 3
Key Pointers
The last move to reach step n was either a single step from n-1 or a double step from n-2 — so ways(n) = ways(n-1) + ways(n-2), the Fibonacci recurrence.
Only the last two values are ever needed, so O(1) space beats a full DP array.
Base cases: 1 way to stand on step 1, 2 ways to stand on step 2.
Step-by-Step Analysis
Handle small n directly: if n ≤ 2, the answer is n itself.
Initialize two running values: one_back = 2 (ways to reach step 2), two_back = 1 (ways to reach step 1).
For each step from 3 up to n, compute current = one_back + two_back, then shift both values forward by one step.
Return one_back once the loop finishes — it now holds the count for step n.
Complexity
Time: O(n) — Space: O(1)
Code
def climbStairs(n: int) -> int:
if n <= 2:
return n
one_back, two_back = 2, 1
for _ in range(3, n + 1):
one_back, two_back = one_back + two_back, one_back
return one_back
Code Explanation
How the solution above works, piece by piece.
if n <= 2: return n: 1 step has 1 way; 2 steps have 2 ways (1+1 or 2). These are the base cases.
The key idea: your last move onto step i was either a 1-step from i − 1 or a 2-step from i − 2, so ways(i) = ways(i − 1) + ways(i − 2).
one_back, two_back = 2, 1: ways(2) and ways(1), the two most recent answers.
Each loop computes the next answer as one_back + two_back and shifts the window: the old one_back becomes two_back. Python's tuple assignment does both at once, so no temp variable is needed.
After the loop, one_back holds ways(n). O(n) time and O(1) space, instead of O(n) space for a full table or O(2ⁿ) time for plain recursion.
Visual Walkthrough
For n = 3, extended to 5 so the pattern is visible:
Why it adds up
The two variables in the code (the page's example stops at step 3 → answer 3)
Only the last two answers are ever needed, so two variables replace a whole DP table. The page example n = 3 gives 3; steps 4 and 5 show the pattern continuing (it's the Fibonacci sequence).