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.
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 fails: 45 steps allow 1836311903 of them. Every climb to step n stands on step n-1 or step n-2 right before its last move, so ways(n) = ways(n-1) + ways(n-2), the Fibonacci recurrence. Build 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, one that ends with a 2-step stood on step n-2, and no climb ends both ways, so the two counts add. One step has one climb and two steps have two, so return n when n ≤ 2.
The recursion forgets what it has computed. climbStairs(5) asks for step 3 twice and step 2 three times, 9 calls in all, and n = 45 takes 2269806339 calls.
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 count for step k depends on k alone, so it never changes once known. Write it into a memo slot the first time you compute it, and every later request reads the slot instead of recursing. Each count from step 3 to step n is then computed once, with one addition: O(n) time. For n = 5 the second request for step 3 is a lookup.
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
Build upward instead. When you compute the count for step k, only the counts for k-1 and k-2 are read, and nothing older is needed again. So two variables replace the memo.
For n = 5 the pair (prev, curr) moves from (1, 2) to (2, 3), (3, 5) and (5, 8), and curr = 8 is the answer. 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
- Wrong base cases. Two steps have two climbs,
1, 1and2. Returning 1 forn = 2shifts every later answer: you get 2 forn = 3instead of 3. - Counting choices instead of sequences. Counting only how many 2-steps you take gives
n/2 + 1, which is 3 forn = 5instead of 8. - Filling a table without a guard. With
n = 1, a table ofn + 1 = 2slots has no room for step 2. Returnnfirst whenn ≤ 2. - Running one step too far. The count for 46 steps is 2971215073, which overflows a 32-bit
intto a negative number in Java, C or C#.
Frequently asked questions3
Why is Climbing Stairs a Fibonacci problem?
Each climb to step n ends with a 1-step from n-1 or a 2-step from n-2, which is the Fibonacci rule. With ways(1) = 1 and ways(2) = 2 the counts run 1, 2, 3, 5, 8, 13: 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: O(n) time and O(1) extra space. Recursion with a memo is O(n) time and O(n) space. The plain recursion is exponential, with a call count that grows by a factor of about 1.618 per step.
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.
def climbStairs(n):
# Write code hereTest #1
Test #2
Argument
n = 3
Expected Output
3