🦶70. Climbing Stairs

Grind 75 | Easy | July 25, 2022

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 = 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

Example 2

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

This is a relatively easier question compared to the ones we have solved before. Given that I had done the coin change problem before this, I knew to apply the same idea of dynamic programming here. We are given an integer n, and we can either take 1 or 2 steps. The steps is essentially the number of coins and n is the amount in our coin change problme. So, like we did in coin change, we will follow similar steps. We will calculate the unique number of ways to climb for every value starting at 1 till n. This way, we break the original problem into smaller problem until it becomes easy to answer.

Example 1, our n is 3 and we have coin 1 and 2. In order to find the uniques climbing ways for 3, we need to start at 1 and go all the way till three. NOTE: we will say that if n is 0, the ways to climb is 1. The reason why we start with this assumption will be clear in second. n = 1, then if we take 1 step, we can climb n. we cannot climb 1 with our step size 2. Therefore, when n = 1, number of unique ways to climb is 1. n = 2, when n is 2, we can directly take 2 steps or we could take 1 + 1 steps. That gives us two unique ways to climb the stairs.

ALGORITHM: we subtract n by both the possible steps (2 and 1 in this case). 2 - 1 gives you 1. We know that for n = 1, there is 1 unique way. Next, 2 - 2 = 0. When we started we made the assumption that if n = 0, unique ways is 1. So 2 - 2 = 0 which results in 1 unique ways. Sum all unique ways you get when you subtract n by 1 and 2 and that will be your answer for n. We got 1 when we subtracted n(2 in this case) by 1 and we got 1 unique way when we subtracted n(2 in this case) by 2. In total we get 2 unique ways to climb when n = 2.

n = 3. We will use the algorithm we developed. We first subtract 3 - 1 = 2. We found earlier that there are 2 unique ways when n = 2. Next, we subtract 3 - 2 = 1. We know that when n = 1, there is 1 unique way. So, our final sum or the number of unique ways to climb n =3 is 3(2+1).

class Solution:
    def climbStairs(self, n: int) -> int:
        # store the number of ways we can climb for values from 0 -> n
        # NOTE: when n = 0, we say we can take 1 step 
        ways = [1]
        
        for i in range(1, n+1):
            number_of_ways = 0
            
            # make sure the subtraction is not negative
            if i - 1 >= 0: 
                number_of_ways += ways[i-1]
            
            if i - 2 >= 0: 
                number_of_ways += ways[i-2]
            
            ways.append(number_of_ways)
        
        return ways[n]