LeetCode Question: Climbing Stairs
The question is fairly simple:
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Some examples of this:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 stepsInput: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
I paired up with some people from Flatiron to work on this as mock interview practice and one of them suggested we start by writing out the solutions which was a good idea.
1: 1
Total solutions: 12: 11 2
Total solutions: 23: 111 21 12
Total solutions: 34: 1111 211 121 211 22
Total solutions: 55: 11111 2111 1211 1121 1112 221 212 122
Total solutions: 8
From the pattern here, we see this is like the Fibonacci Sequence, where you just add the previous two numbers.
We started with a base case, which is that 1 has a solution of 1.
And then we build on top of that with a recursive function, passing in n-1 and n-2 as parameters, to add the previous two solutions up.
That’s as far as we got though. As elegant as this solution is and although it only takes 2 lines of code, the run time is definitely not ideal, as it runs with O(n²).
Nonetheless, it was good to connect with students from different cohorts and to talk out loud about the solutions.
