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. 1 step + 1 step
  2. 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

Similar Posts