Climbing Stairs
Climbing Stairs is LeetCode 70 (Easy). A staircase has n steps and you start at the bottom. Each move climbs either 1 step or 2 steps. Return how many distinct ways there are to reach the top.
Two ways to climb stairs are different when their sequences of moves differ, so order matters.
- 1 <= n <= 45
Intuition
Do not try to build routes from the bottom. Look at the last move instead. To stand on step n, your final move was either a 1-step from n-1 or a 2-step from n-2. Every route to n-1 extends to n in exactly one way, and so does every route to n-2. No route is in both groups, because the last move differs, so the two counts simply add.
That makes the number of ways to climb stairs the Fibonacci recurrence: each value is the sum of the two before it. Since nothing older is ever needed, this climbing stairs dynamic programming solution only has to remember two numbers.
A count of ways to reach a target, where each move uses a small fixed set of sizes and order matters. Split by the last move and add the groups. With moves {1, 2} it is Fibonacci; with moves {1, 2, 3} it is the same idea with three terms.
Approach
Before reading on, count the ways for n = 1, 2, 3 and 4 by hand. Do you see how each answer is built from the previous two? Aim for O(n) time and O(1) space.
Two ways to solve it
Start at steps 0 and 1 and walk up to n, keeping only the last two counts in prev and cur.
- Space: two integers, however large
nis. - Speed: one addition per step, no calls or lookups.
- Safety: no recursion, so no stack limit.
This is the version to write in an interview.
Write ways(i) = ways(i-1) + ways(i-2) as a recursive function and cache each result so it is computed once.
- Space: a cache entry and a stack frame per step.
- Speed: n real calls; every repeat is a cache hit.
- Readability: the code is the recurrence, word for word.
A natural fix for plain recursion, but the loop is leaner.
Both compute each ways(i) once, so both run in O(n) time; the loop wins because it keeps two numbers instead of a cache and a call stack. The steps, code and live demo below follow the loop, and the memoized code is further down.
Define the count by the last move
Let ways(i) be the number of distinct routes that end on step i, so the answer is ways(n). Splitting the routes by their last move gives ways(i) = ways(i-1) + ways(i-2), which depends only on answers for lower steps.
Fix the base cases
ways(0) = 1: the empty route (standing still).ways(1) = 1: a single 1-step.
Check: ways(2) = 1 + 1 = 2, matching 1+1 and 2. Using ways(0) = 0 shifts every later answer.
Avoid plain recursion
Calling f(n-1) + f(n-2) recursively recomputes the same steps again and again: about 2^n calls, far too slow for n = 45. Either memoise it (cache each f(i)) or build the answers upward in a loop.
Keep two variables instead of an array
Walk i from 2 to n holding prev = ways(i-2) and cur = ways(i-1), and set prev, cur = cur, prev + cur each time. Only the last two values feed the next one, so an array of size n would be wasted memory: time stays O(n) and space drops to O(1).
Climbing Stairs solution in Python | C++ | Java
Memoized recursion
ways(i) returns 1 for steps 0 and 1, and otherwise adds ways(i-1) and ways(i-2). The cache stores each answer the first time, so later calls return it at once.
Common pitfalls
Recursing without memoisation
def climbStairs(self, n):
if n <= 1:
return 1
return self.climbStairs(n - 1) + self.climbStairs(n - 2)prev, cur = 1, 1
for _ in range(2, n + 1):
prev, cur = cur, prev + curThe recursion tree has about 2^n nodes because f(n-2) is computed inside f(n-1) and again on its own. At n = 45 that is billions of calls and a time-out. The loop computes each value once.
Starting from ways(0) = 0
prev, cur = 0, 1
prev, cur = 1, 1
The empty route to step 0 is what a 2-step onto step 2 extends. With 0 there, ways(2) comes out as 1 and every answer is shifted by one position.
Updating the two variables one after the other
prev = cur cur = prev + cur
prev, cur = cur, prev + cur
The first line overwrites prev before the second reads it, so cur doubles each time and you get powers of two. Use simultaneous assignment in Python or a next temporary in C++ and Java.
Edge cases
Return 1. The two-variable loop simply does not run. An array version that writes dp[2] would index past a size-2 array, which is why array solutions special-case it.
The answer is 1,836,311,903, which fits in a 32-bit signed int. From about n = 46 it would overflow int.
Complexity
Climbing Stairs FAQ
What is the climbing stairs problem?
Given n stairs, where each move climbs 1 or 2 steps, count the distinct ordered sequences of moves that reach the top. For n = 3 the answer is 3: 1+1+1, 1+2, 2+1.
How does the climbing stairs solution work, step by step?
- State:
ways(i)= number of distinct routes to stepi. - Recurrence: the last move is +1 from
i-1or +2 fromi-2, and these groups are disjoint, soways(i) = ways(i-1) + ways(i-2). - Base cases:
ways(0) = 1,ways(1) = 1. - Computation: loop
ifrom 2 tonkeeping two variables. - Complexity: O(n) time, O(1) space.
- Example:
n = 5gives 8.
Why is climbing stairs a Fibonacci problem?
Because each answer is the sum of the two previous answers, and the starting values are 1 and 1. That is the definition of the Fibonacci sequence, so ways(n) = F(n+1).
Is climbing stairs dynamic programming?
Yes. It has overlapping subproblems (the same ways(i) is needed many times) and optimal substructure (the answer for n is built from answers for smaller steps). The loop is bottom-up DP with the table reduced to two variables.