Climbing Stairs easy
Description
You are climbing a staircase with n steps. Each move, you can climb either 1 step or 2 steps. How many distinct ways are there to reach the top?
Examples
> Case 1:
Input: n = 2
Output: 2 # (1+1) or (2)
> Case 2:
Input: n = 3
Output: 3 # (1+1+1), (1+2), (2+1)
> Case 3:
Input: n = 4
Output: 5 # (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2)Constraints
1 <= n <= 45
Intuition
Apply the three-question recipe:
- Base case: at
n = 0you’ve reached the top — exactly 1 way (the empty sequence of moves). Atn = 1, also 1 way (a single 1-step). - Recursive case: the last step is either a 1 or a 2. So
ways(n) = ways(n - 1) + ways(n - 2). - Combine: add.
That recurrence is Fibonacci in disguise — ways(n) = fib(n + 1).
Just like naive Fibonacci, this branches twice per call — O(2^n). We’ll fix it with memoization or a bottom-up loop.
Approach 1: Naive recursion (don’t actually submit this)
Time O(2^n), space O(n) for the call stack. n = 45 would take ages — TLE on any judge.
Approach 2: Memoized recursion (linear)
Time O(n), space O(n).
Approach 3: Bottom-up with O(1) space
We only need the last two values at any moment — no array needed.
Time O(n), space O(1) — best of both worlds.
Climbing Stairs is the Hello World of dynamic programming. The exact same recurrence appears in: tile-laying problems, decode-ways, count-paths-in-a-grid, and Fibonacci itself. Recognize the shape and you have the answer.
Analysis
| Approach | Time | Space |
|---|---|---|
| Naive recursion | O(2^n) | O(n) |
| Memoized | O(n) | O(n) |
| Bottom-up O(1) | O(n) | O(1) |