Climbing Stairs

You are given an integer n representing the number of steps to reach the top of a staircase. You can climb with either 1 or 2 steps at a time.

Return the number of distinct ways to climb to the top of the staircase.

1. 1 + 1 = 2
2. 2 = 2

1. 1 + 1 + 1 = 3
2. 1 + 2 = 3
3. 2 + 1 = 3

Approach

This is the Fibonacci sequence: to reach step i, you can come from i-1 or i-2. Track only the last two values and iterate up to n.

Why It Works

Every valid way to reach step i ends with a jump from i-1 or i-2, so the total ways are the sum of those two subproblems. Iterating computes these values in order.

Complexity

• Time: O(n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for _ in range(3, n + 1):
            prev2, prev1 = prev1, prev1 + prev2
        return prev1