Leetcode qs.70
Python code solution and explanation

Question

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

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

Thoughts

First, let’s try to recognize patterns that come with increasing n. 

3 has 3 combinations to reach the top

1. 1 step + 1 step + 1 step
2. 1 step + 2 step
3. 2 step + 1 step

4 has 5 combinations to reach the top

1. 1 step + 1 step + 1 step + 1 step
2. 2 step + 2 step
3. 1 step + 1 step + 2 step
4. 2 step + 1 step + 1 step
5. 1 step + 2 step + 1 step

5 has 8 combinations to reach the top

1. 1 step + 1 step + 1 step + 1 step + 1 step
2. 1 step + 1 step + 1 step + 2 step
3. 1 step + 1 step + 2 step + 1 step
4. 1 step + 2 step + 1 step + 1 step
5. 2 step + 1 step + 1 step + 1 step
6. 1 step + 2 step + 2 step
7. 2 step + 2 step + 1 step
8. 2 step + 1 step + 2 step

We can visualize this in another way. For this example, let’s go backward, starting from 5. Now, how many combinations can you take from step 5 to end up at step 5? 1 obviously. Now, how many combinations can you take from step 4 to end up at step 5? Again, it’ll be 1. From step 3, there are 2 combinations of getting to step 5. Notice how we can add the 2 numbers in front of the array, to get the number before it.

For example, if we want to know how many combinations there are to go from step 2 to step 5, you can simply look at the 2 numbers in front of it (2 and 1), and add them up, where it will equal 3. We can keep on doing this until we get to step 0, our initial start position. At that point, we can see that if there are 5 steps, there are 8 different combinations to reach there.

Notice how the last two numbers in the array will always stay the same, whether n = 3 or
if n = 100. That means we don’t need to make any array in the first place. We just need two variables, both initially equalling 1, which is used range(n - 1) times.

Solution

Now that we’ve brainstormed and recognized a pattern, we can jump into the solution. As stated before, we can start by setting x and y both to equal 1.

        x = 1
        y = 1

Now we can make a loop, which will be repeated range(n - 1) times. Basically, this loop will use the first two numbers in the array, add them up, and use that as the next number. This loop will repeat n - 1 times. 

        for _ in range(n - 1):
            total = x + y
            x = y
            y = total

When the previous loop ends, total will equal the solution, so we can simply return the solution. 

        return total

Code

class Solution:
    def climbStairs(self, n: int) -> int:
        x, y = 1, 1
 
        for _ in range(n - 1):
            total = x + y
            x = y
            y = total
 
        return total

Example run

n = 6. loop will repeat n – 1 (5) times.

total = 2  |  1 + 1 = 2
x = 1
y = 2

total = 3  |  1 + 2 = 3
x = 2
y = 3

total = 5  |  2 + 3 = 5
x = 3
y = 5

total = 8  |  3 + 5 = 8
x = 5
y = 8

total = 13  |  5 + 8 = 13
x = 8
y = 13

return total

CONCLUSION

We started off by trying to find a pattern, and eventually, we recognized one. We realized that we only needed two variables and a for loop to make this work. We made a seemingly complex problem into a simple solution, with only 5 lines of code.