Climbing Stairs (LeetCode 70)

The problem

You are at the bottom of a staircase with n steps. Each move climbs either 1 step or 2 steps. Return how many different sequences of moves take you exactly to the top. The input is a single integer n (at least 1).

Input:  n = 5
Output: 8

There are 8 orderings of 1s and 2s that add up to 5, for example 1+1+1+1+1, 2+2+1, 1+2+2 and 2+1+2.

How to think about it

Start with brute force. Recursively try both moves from every step: ways(n) = ways(n-1) + ways(n-2), with a direct recursive call for each. It is correct, but the call tree doubles at each level, so it is O(2ⁿ). ways(3) gets recomputed again and again from different branches.

The key insight: look at the last move. Every way to reach step n ends with either a 1-step (from n-1) or a 2-step (from n-2). Those two groups don’t overlap and together cover everything, so ways[n] = ways[n-1] + ways[n-2]. That is the Fibonacci recurrence, with ways[0] = 1 (one way to stand still) and ways[1] = 1.

Only two values matter. Each answer depends on the previous two and nothing older. So instead of a whole table, keep two rolling variables and slide them forward n times. That turns exponential recursion into a single O(n) loop with O(1) memory.

Which pattern is this? 1-D dynamic programming. The tell is “count the ways” where each choice moves you a small fixed distance, so the answer for n is built from the answers just below it.

Approach

1. Let a = ways[0] = 1 and b = ways[1] = 1.
2. Repeat n times: shift the window forward with a, b = b, a + b.
3. After i shifts, a holds ways[i]. After n shifts, return a.

Solution

def climb_stairs(n):
    a, b = 1, 1                                   # ways[0], ways[1]
    for _ in range(n): a, b = b, a + b            # slide: ways[i] = ways[i-1] + ways[i-2]
    return a
# climb_stairs(5) -> 8

Dry run

For n = 5, the values after each pass of the loop:

After 5 passes a = 8, so the answer is 8.

Complexity

• Time: O(n). The loop runs n times and does constant work each time.
• Space: O(1). Only two integers are stored, no matter how large n is.

Edge cases and pitfalls

• n = 1 returns 1 and n = 2 returns 2; both fall out of the loop with no special case.
• Off-by-one in the base case. Starting from ways[1] = 1, ways[2] = 2 is also fine, but then the loop count changes. Pick one convention and trace n = 1 to check it.
• Plain recursion without memoisation times out around n = 40. If you write it top-down, add @lru_cache.
• Big numbers. Python integers don’t overflow; in Java or C++ the count for large n would need a 64-bit type.

Related problems

• Min Cost Climbing Stairs (LeetCode 746): the same two-predecessor shape, but minimising cost instead of counting.
• Decode Ways (LeetCode 91): Climbing Stairs where each 1-step or 2-step is only allowed if the digits are valid.
• House Robber (LeetCode 198): another “look at the last choice” recurrence with two rolling variables.