# [LeetCode] Top Interview 150 Problems Solving # 70 Climbing Stairs

# **Understanding the Problem**

A number is given as `n`. Imagine that only 1 or 2 steps could be taken at once to reach the number `n`. For instance, if the number is 4, there are 5 ways to reach number 4.

```python
n = 4

# ways to reach n
1, 1, 1, 1 # 1
2, 1, 1 # 2
1, 2, 1 # 3
1, 1, 2 # 4
2, 2 # 5
```

So the return number should be 5.

# **Approach**

I was attempting to solve the problem with mathematical approach, but I could not find a pattern by dividing by 2 or other methods.

After some trials, I was manually enumerating the ways to reach the number and found out that there was a pattern, which each number was a output of the sum of the previous 2 numbers. With this hint, I used a loop to complete the task.

# **Solution**

The first 3 numbers were okay to return itself. So I returned `n` if the number is less or equal to 3. And I took the steps as follow.

1. The number starts at least from 4, so I declared `nums = [1, 2, 3]` first, and `count = 3`
    
2. In the `while` loop, it appends to `nums` the sum of the last two numbers by accessing with `nums[-1]` and `nums[-2]`
    
3. Eventurally return `nums[-1]`
    

```python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 3:
            return n

        nums = [1, 2, 3]
        count = 3
        
        while count < n:
            nums.append(nums[-1] + nums[-2])
            count += 1

        return nums[-1]
```

# **Reflection**

It took some time to solve the problem until I figured out the pattern of the steps. This time I learned also that sometimes manually enumerating to find some patterns in problems like this will help finding the solution, yet it is not always the best practice though.