Climibing stairs

"""
Intuition:
To reach the i-th step, you have only two possible moves:
1. Come from (i-1)-th step by taking 1 step
2. Come from (i-2)-th step by taking 2 steps

So, total ways to reach step i =
    ways(i-1) + ways(i-2)

This works because:
- All paths that end at (i-1) can extend by 1 step
- All paths that end at (i-2) can extend by 2 steps
- These two sets are disjoint and cover all possibilities

Base cases:
ways(1) = 1
ways(2) = 2
"""
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        prev1 = 1  # ways to reach step 1
        prev2 = 2  # ways to reach step 2

        for i in range(3, n + 1):
            curr = prev1 + prev2
            prev1 = prev2
            prev2 = curr

        return prev2