Python LeetCode 70: Climbing Stairs – (Easy)
Problem
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
Code
def climbStairs(self, n: int) -> int:
# if less than or equal to 2 steps, we know there's 1 way or 2 ways.
if n <= 2:
return n
# create an array of N size to store our `ways` setting all values to 0
step_ways = [0] * (n + 1)
# set ways index 1 and 2 to `1` and `2` (reprensenting 1 step and 2 step)
step_ways[1], step_ways[2] = 1, 2
# loop over the array from point 3 -> end, implementing fibonnaci algoritm n = (n-1 + n-2)
for i in range(3, n + 1):
step_ways[i] = step_ways[i-1] + step_ways[i-2]
return step_ways[n]
Approach
This problem is basically just the fibonacci sequence, in that to get step 3 upwards, you can take the methods of getting there from the previous two ways and add them together.
For example:
Step 1 = 1
Step 2 = 2 (1 + 1, or 2)
Step 3 = 3 (1 + 1 + 1, 2 + 1 , 1 + 2)
Step 4 = 5 (1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2)
Think about how you can reach say step 11:
If Last step was a single step:
To get to step 11 by taking a 1-step jump, you must have been on step 10 just before.
So all ways to reach step 10 can lead to step 11 by adding a 1-step jump, so we can add 1 step to all the pre-existing ways to get 10.
Last step was a double step:
To get to step 11 by taking a 2-step jump, you must have been on step 9 just before.
So all ways to reach step 9 can lead to step 11 by adding a 2-step jump, so we can add 2 step to all the pre-existing ways to get 10.
note: below n relates to the current step number we’re trying to work out:
So if we all the ways you got to 10 (n-1) and all ways you got to step 9(n-2) you know all the ways you can get to 11. Cos we can deduce you’ve got there either by adding 1 or adding 2.
So you may have noticed ways = ways(n-1) + ways(n-2) looks familiar, its the same as the Fibonacci sequence Fib(k) = Fib(k-1) + Fib(k-2)
Therefore we can simply write this as code -> (i’ve added comments to explain in code rather than here)
As always feel free to drop me a follow on DevTo or twitter/x