Climbing Stairs

Climbing Stairs looks like a counting puzzle, but it is secretly the Fibonacci sequence in disguise. It is the perfect first taste of dynamic programming: break a big count into smaller counts you have already solved.

The idea

Ask one question about the last move: how did you arrive at stair n? There are only two possibilities. Either you took a 1-step from stair n − 1, or a 2-step from stair n − 2. Those two groups never overlap and cover every path, so:

ways(n) = ways(n − 1) + ways(n − 2)

That is exactly Fibonacci. A naive recursion would recompute ways(n − 2) again and again — the same subproblems overlap, which makes plain recursion O(2ⁿ). The fix: solve each small count once and store it in an array dp, where dp[i] = ways to reach stair i. Then build up from the bottom.

Seed the two base cases — dp[0] = 1 (one way to stand still at the bottom) and dp[1] = 1 (one 1-step) — then fill every cell left to right. The last cell, dp[n], is the answer.

Walk through it

Step through the animation. The first two cells are seeded as base cases. Then the pointer i moves right one cell at a time. At each cell we read the two cells just behind it (they light up), add them, and write the sum into dp[i]. The dp line underneath shows the array filling up: 1, 1, 2, 3, 5, 8. The final cell dp[5] = 8 is our answer.

Pseudocode

if n is 0 or 1: return 1
make an array dp of size n + 1
dp[0] = 1                 # one way to stay at the bottom
dp[1] = 1                 # one way to reach the first stair
for i from 2 to n:
    dp[i] = dp[i-1] + dp[i-2]   # arrive from one below or two below
return dp[n]

The whole method is two base cases plus one line of addition repeated n − 1 times.

The Python solution

def climb_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        # arrive from one step below or two below
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

• dp has one slot per stair, from 0 up to n.
• dp[0] = 1 and dp[1] = 1 are the base cases — the smallest counts we know without computing.
• The loop fills each cell from the two before it. By the time we reach dp[i], both dp[i-1] and dp[i-2] are already final, so the addition is O(1).
• return dp[n] hands back the count for the top stair.

(Tiny note: this exact code assumes n >= 1. For a fully safe version, return 1 early when n == 0.)

Complexity

We trade O(n) extra space (the dp array) to collapse exponential work down to a single linear pass. You can even drop the array and keep just the last two values, which makes it O(1) space — the same trick used for Fibonacci.

When this pattern shows up

Practice