---

Intuition

The problem is essentially about finding the number of distinct ways to climb n stairs, where you can take either 1 or 2 steps at a time. Observing the pattern, we see that this problem is related to the Fibonacci sequence, where each number is the sum of the previous two. This is because the number of ways to reach the nth stair is the sum of:

1. The ways to reach the (n-1)th stair (by taking a single step), and

2. The ways to reach the (n-2)th stair (by taking a double step).

---

Approach

1. Iterative Fibonacci Calculation:

   • Start with two base cases, x = 1 (ways to reach the first stair) and y = 1 (ways to reach the second stair).

   • Use a loop to compute the Fibonacci sequence iteratively, updating x (current step count) and y (previous step count) at each iteration.

   • This avoids recursion and the overhead of recalculating sub-problems, making it efficient.

2. Return Result:

   • After n-1 iterations, x will hold the number of distinct ways to climb n stairs.

---

Complexity

• Time complexity:
  $$O(n)$$
  The loop runs n-1 iterations, so the time complexity is linear with respect to n.

• Space complexity:
  $$O(1)$$
  Only two variables, x and y, are used, so the space usage is constant.

---

Code

class Solution(object):
    def climbStairs(self, n):
        x, y = 1, 1

        for i in range(n - 1):
            temp = x
            x = x + y
            y = temp

        return x

---

Example Test Cases

1. Input: n = 2
   Output: 2
   Explanation: Two ways: (1 step + 1 step) or (2 steps).

2. Input: n = 3
   Output: 3
   Explanation: Three ways: (1+1+1), (1+2), or (2+1).

3. Input: n = 5
   Output: 8
   Explanation: Eight ways: Follows the Fibonacci sequence.

---

Connect with Me

If you found this solution helpful, feel free to connect with me on LinkedIn! Let’s grow and share knowledge together. 😊

---