roadmap/dynamic-programming/Climbing Stairs

Climbing Stairs

EasyAmazonGoogleAppleAdobe

Problem

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Intuition — the key insight

To reach step n, you either came from step n-1 (took 1 step) or step n-2 (took 2 steps). So ways(n) = ways(n-1) + ways(n-2). This is exactly Fibonacci. Base cases: ways(1) = 1, ways(2) = 2.

Approach

1. Recognize the recurrence

ways(n) = ways(n-1) + ways(n-2). Base cases: ways(1) = 1, ways(2) = 2.

2. Bottom-up DP with O(1) space

We only need the previous two values. Use two variables prev1 and prev2, updating them as we go. No array needed.

Complexity

Time

O(n)

Space

O(1)

Single loop from 3 to n. Only two variables maintained regardless of n.

Solution code

Python

def climbStairs(self, n: int) -> int:
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2  # ways(1), ways(2)
    
    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    
    return prev1

Edge cases to remember

⚠n = 1: return 1 directly

⚠n = 2: return 2 (either two 1-steps or one 2-step)

⚠Large n: no overflow risk in most languages for reasonable n

Hints

What pattern do you think this problem uses?