How many distinct ways can you climb n stairs if you can take 1 or 2 steps at a time?

How to think about it

This is usually the first DP question in a loop, and what the interviewer wants to see is whether you can find the recurrence yourself rather than recall that the answer is Fibonacci. The reasoning they are listening for is one sentence: the last move onto stair n was either a single step from n-1 or a double step from n-2, so the count of ways to reach n is just the sum of the ways to reach those two.

That sentence is the whole problem. It hands you ways(n) = ways(n-1) + ways(n-2) directly, and it carries the two DP hallmarks: overlapping subproblems — ways(5) needs ways(4) and ways(3), which both lean on ways(3) and ways(2) — and optimal substructure, since the total from any stair depends only on the two below it. Naive recursion mirrors the recurrence but recomputes those shared calls exponentially, O(2^n). Memoising drops it to O(n) time and O(n) space. But because each value needs only the previous two, you can throw the array away and keep two rolling variables — O(1) space. The base cases are ways(1) = 1 and ways(2) = 2.

A worked example

def climb_stairs(n):
    if n <= 2:
        return n                          # ways(1)=1, ways(2)=2
    prev2, prev1 = 1, 2                    # ways(1), ways(2)
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2   # roll the window forward
    return prev1

print(climb_stairs(1))    # only [1]
print(climb_stairs(2))    # [1,1] or [2]
print(climb_stairs(5))
print(climb_stairs(10))

# Cross-check the fast version against the plain recursion for small n
def climb_recursive(n):
    if n <= 2: return n
    return climb_recursive(n - 1) + climb_recursive(n - 2)

print(all(climb_stairs(i) == climb_recursive(i) for i in range(1, 15)))

1
2
8
89
True

The first four lines are the Fibonacci shift in disguise: 1, 2, 8, 89. There is exactly one way up a single stair and two ways up two; by five stairs there are eight distinct step sequences, and by ten there are eighty-nine. The closing True is the part worth saying out loud — it confirms the O(1)-space iteration agrees with the literal recursive definition for every n from 1 to 14, so the optimisation did not quietly change the answer.