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.

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]

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.