Climbing Stairs
You stand at the bottom of a staircase with n steps. Every move climbs either 1 step or 2 steps. Two climbs count as different when their sequences of moves differ, so 1, 2 and 2, 1 are two ways. Your function gets n and returns the number of distinct ways to reach the top.
Function
- ninteger
- the number of steps in the staircase
- Returnsinteger
- the number of distinct sequences of 1-steps and 2-steps that reach step n
Constraints
1 ≤ n ≤ 45- The answer fits in a signed 32-bit integer:
n = 45gives1836311903.
Examples
- Input
- n = 3
- Output
- 3
- Explanation
- Three steps can be climbed as
1, 1, 1, as1, 2or as2, 1, so there are 3 ways.
- Input
- n = 5
- Output
- 8
- Explanation
- Every climb to step 5 ends with a 1-step from step 4 (5 ways to get there) or a 2-step from step 3 (3 ways), so the answer is
5 + 3 = 8.
+13 hidden tests on Submit
Follow-up
What if some steps are broken and you may never stand on them? How does the recurrence change, and what is the count for a broken step?
Hints
Open them one at a time. Each one gives away a little more.
Look at the last move of any climb to step
n. Where could you have been standing right before it?Every climb to step
nends with a 1-step from stepn-1or a 2-step from stepn-2, never both. So the count fornis the count forn-1plus the count forn-2.Start from the counts for 1 step (1 way) and 2 steps (2 ways) and work upward. You only ever need the last two counts, and each new count is their sum.
Solution
Listing every climb does not work: a 45 step staircase has 1836311903 of them. The way in is the last move. Every climb to step n passes through step n-1 or step n-2 right before the end, which gives ways(n) = ways(n-1) + ways(n-2), the Fibonacci recurrence. Compute it from the bottom up and two variables are all you need.
Plain recursion on the last move
Correct, but does not finish on the largest tests
Intuition
Split the climbs to step n by their last move. A climb that ends with a 1-step stood on step n-1 before it, and there are ways(n-1) such climbs. A climb that ends with a 2-step stood on step n-2, and there are ways(n-2) of those. Every climb ends one way or the other and none ends both ways, so ways(n) = ways(n-1) + ways(n-2).
The recursion needs two base cases. One step has one climb, and two steps have two climbs (1, 1 and 2). In both cases the answer equals n, so the function returns n when n ≤ 2 and the sum otherwise.
The answer is right, but the work explodes. climbStairs(5) asks for step 3 twice and step 2 three times, 9 calls in all, and the call count grows like the answers themselves. For n = 45 the function makes 2269806339 calls, about 2.3 × 10^9, far too many for a time limit. The recursion is only n levels deep, so the stack uses O(n) space.
Algorithm
- If
n ≤ 2, returnn. - Count the climbs that reach step
n-1with a recursive call. - Count the climbs that reach step
n-2with a second recursive call. - Return the sum of the two counts.
def climbStairs(n):
if n <= 2:
return n # 1 step: one way, 2 steps: two ways
return climbStairs(n - 1) + climbStairs(n - 2)Recursion with a memo
Intuition
The recursion is slow only because it forgets. Each count depends on k alone, so once you know the count for step k it never changes. Keep a memo, an array with one slot per step, and write each count there the first time you compute it. Every later request for the same step reads the slot instead of recursing again.
Now each of the counts from step 3 to step n is computed once, with one addition. For n = 5 the calls go down to step 2 once, then the answers come back up as 3, 5 and 8, and the second request for step 3 is a lookup. That is O(n) time instead of billions of calls.
The memo holds n + 1 numbers and the recursion is still n levels deep, so the space is O(n). A 0 in a slot means not known yet, which is safe because every real count is at least 1.
Algorithm
- Create a memo with
n + 1slots, all 0. - In the recursive helper, return
kwhenk ≤ 2. - If the memo slot for
kis 0, fill it with the helper's results fork-1andk-2added together. - Return the memo slot.
- Call the helper on
n.
def climbStairs(n):
memo = [0] * (n + 1) # memo[k] = ways to reach step k, 0 = not known yet
def ways(k):
if k <= 2:
return k
if memo[k] == 0:
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)Bottom up with two variables
Intuition
Turn the recursion around. Instead of starting at the top and asking downward, start at the bottom and build upward. When you compute the count for step k, the counts for k-1 and k-2 are already known, and nothing older is ever read again. So two variables replace the whole memo.
Let prev hold the count for step k-2 and curr the count for step k-1. Start with prev = 1 and curr = 2, the counts for steps 1 and 2. On each step add them into next, then slide the pair forward. For n = 5 the pair moves from (1, 2) to (2, 3), (3, 5) and (5, 8), and curr = 8 is the answer.
The loop runs n-2 times with one addition each, O(n) time, and keeps three integers, O(1) space. Compute next before you overwrite prev, or the sum uses the wrong value.
Algorithm
- If
n ≤ 2, returnn. - Set
prev = 1andcurr = 2. - For
kfrom 3 ton, computenext = prev + curr, then setprev = currandcurr = next. - Return
curr.
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(n - 2):
prev, curr = curr, prev + curr
return curr
Pitfalls and edge cases
The recurrence is short, so most bugs sit in the base cases, the running time and the 32-bit limit.
- Handing in the plain recursion. It passes the small tests and then needs about
2.3 × 10^9calls forn = 45. Store each count once. - Wrong base cases. Two steps have two climbs,
1, 1and2. Returning 1 forn = 2shifts every later answer: you would get 2 forn = 3instead of 3. - Counting choices instead of sequences.
1, 2and2, 1are two climbs. Counting only how many 2-steps you take givesn/2 + 1, which is 3 forn = 5instead of 8. - Filling a table without a guard. With
n = 1a table ofn + 1 = 2slots has no room for the count of step 2. Returnnright away whenn ≤ 2. - Running one step too far. The count for 45 steps, 1836311903, fits in 32 bits, but the count for 46 steps is 2971215073 and does not. A loop that computes one extra value overflows to a negative number in Java, C or C#.
Frequently asked questions4
Why is Climbing Stairs a Fibonacci problem?
Every climb to step n ends with a 1-step from n-1 or a 2-step from n-2, so ways(n) = ways(n-1) + ways(n-2). That is the Fibonacci rule. With ways(1) = 1 and ways(2) = 2 the counts run 1, 2, 3, 5, 8, 13, which is the Fibonacci sequence shifted by one place: ways(n) = F(n+1).
What is the time complexity of Climbing Stairs?
The bottom up loop does n-2 additions, so it runs in O(n) time with O(1) extra space. The plain recursion is exponential: its call count grows by a factor of about 1.618 per step and reaches 2269806339, roughly 2.3 × 10^9, at n = 45. Memoization brings the recursion down to O(n) time and O(n) space.
What is the difference between memoization and the bottom up solution?
Memoization keeps the recursive function and caches each result the first time it is computed, so it works top down and needs the call stack and a table. The bottom up loop computes the counts in increasing order, so every value it needs is already known and no recursion is involved. Both do O(n) work. The loop also lets you drop the table and keep two numbers.
How do you solve Climbing Stairs with steps of 1, 2 or 3?
Split the climbs by their last move again: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). Start from ways(0) = 1 (the empty climb), ways(1) = 1 and ways(2) = 2, and keep the last three counts instead of two. The time stays O(n) and the space O(1).
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def climbStairs(n):
# Write code hereCase 1
Case 2
Input
n = 3
Expected
3