Climbing Stairs
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
You climb n stairs taking 1 or 2 steps at a time. In how many distinct ways can you reach the top?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many ways to reach stair 1? Stair 2?
- Hint 2Where could you have been one move before standing on stair n?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Reaching the 5th stair of your building. You stood either on stair 4 and took one step, or on stair 3 and took two. So the number of ways to stand on stair 5 is the ways to stand on stair 4 plus the ways to stand on stair 3. Keep writing the count for each stair on the wall, from the bottom: you only ever look at the last two numbers.
- The obvious way
Recursion that tries 1 or 2 steps from every stair repeats work: O(2^n).
- The key insight
Ways to reach the first two stairs are both 1. Every next stair's count is the sum of the previous two. Keep only those two numbers and walk up.
- The algorithm
- Start with two counters, both 1.
- For each further stair: new = sum of the counters.
- Shift: the old newer becomes the older.
- After the last stair, the newer counter is the answer.
Watch it run
Examplen = 5
Stair 1: one way. Stair 2: two ways (1+1 or 2).
1, 2
Where people slip
- The answer for n = 1 is 1: the loop must not run at all then.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def climb_stairs(n):
ways_two_back, ways_one_back = 1, 1 # ways to reach stair 0 and stair 1
for _ in range(n - 1):
ways_two_back, ways_one_back = ways_one_back, ways_one_back + ways_two_back
return ways_one_backNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.