DSA Climbing Stairs

The problem

The climbing stairs problem counts the ways to climb a staircase. Each move climbs one step or two steps. The question asks how many different move sequences reach the top.

The input is n, the number of steps. The output is one count. Reaching the bottom, step 0, counts as one way, the empty sequence.

cases = [(0, 1), (1, 1), (2, 2), (3, 3), (4, 5), (5, 8), (10, 89)]
for n, expected in cases:
    print("steps", n, "ways:", expected)

Three steps have three ways. They are 1+1+1, 1+2 and 2+1. Five steps have eight ways.

Intuition: plain recursion feels fine

The last move into step n comes from step n - 1 or from step n - 2. So the count for n is the sum of those two counts. Plain recursion states that rule directly.

For two or three steps the recursion feels instant and correct. The trap appears only when the calls are counted. The same small steps are solved again and again.

calls = 0

def ways(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

for n in [3, 5, 10]:
    calls = 0
    print("steps", n, "ways:", ways(n), "calls:", calls)

Ten steps need 177 calls to produce the count 89. Most calls repeat work already done. The answer is right, and the effort is wasted.

Brute force: the recursion, counted honestly

The brute force is that same recursion with no storage. It tries both last moves at every step. It returns the base count 1 for step 0 and step 1.

calls = 0

def ways(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

for n in [10, 15, 20]:
    calls = 0
    result = ways(n)
    print("steps", n, "ways:", result, "calls:", calls)

The call count grows much faster than the answer. Twenty steps need 21891 calls. Each call repeats subproblems that a table would solve once.

Repeated subproblems are the signal. Solve each step once, store its count, and read it back later.

The optimal solution: a table filled upward

The state is ways(n), the number of ways to reach step n. That one sentence defines every cell of the table.

The table starts with ways(0) = 1 and ways(1) = 1. Each later cell adds the two cells before it. The last cell is the answer.

def climb(n):
    if n <= 1:
        return 1
    ways = [0] * (n + 1)
    ways[0] = 1
    ways[1] = 1
    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]
    return ways[n]

for n in [0, 1, 2, 3, 4, 5, 10]:
    print("steps", n, "ways:", climb(n))

All seven cases from section 1 pass. Each step is computed exactly once. No call repeats a finished subproblem.

Walkthrough: building the table for five steps

Watch the table fill for n = 5. Each new cell is the sum of its two neighbours on the left. The printed line shows the table after each step.

ways = [1, 1]
print("start:", ways)
for i in range(2, 6):
    ways.append(ways[i - 1] + ways[i - 2])
    print("after step", i, ":", ways)

Step 2 adds 1 and 1, giving 2. Step 3 adds 2 and 1, giving 3. Step 4 adds 3 and 2, giving 5.

Step 5 adds 5 and 3, giving 8. The last cell holds the answer. It is read straight off the table.

Complexity

The table fills one cell per step with one addition, so the time is O(n).

The table holds n + 1 counts, so the space is O(n), and keeping only the last two counts would cut it to O(1).

calls = 0

def brute(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return brute(n - 1) + brute(n - 2)

def table_steps(n):
    return max(0, n - 1)

for n in [10, 15, 20]:
    calls = 0
    brute(n)
    print("steps", n, "recursion calls:", calls, "table steps:", table_steps(n))

The table work grows in a straight line. The recursion count explodes. Printed counts show the gap without any timing.

Edge cases and pitfalls

Step 0 is the base case that anchors the table. Its count is 1, not 0. Setting it to 0 would zero out every later count built from it.

Step 1 also has exactly one way. A single one-step move reaches it. Larger jumps cannot land on it from below.

def climb(n):
    if n <= 1:
        return 1
    ways = [0] * (n + 1)
    ways[0] = 1
    ways[1] = 1
    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]
    return ways[n]

print("n = 0:", climb(0))
print("n = 1:", climb(1))
print("n = 2:", climb(2))
print("n = 3:", climb(3))

A common slip is starting the table at step 1 with no step 0 cell. The recurrence then reads a cell that does not exist. The table needs both base cells before the loop starts.