Climbing Stairs

Problem

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

Examples

The brute-force approach

Recursively explore every possible sequence of steps. From each position, try taking 1 step and try taking 2 steps, counting all paths that land exactly on step n.

def climb(step):
    if step > n: return 0     # overshot, invalid path
    if step == n: return 1    # reached the top, valid path
    return climb(step + 1) + climb(step + 2)

return climb(0)

The call tree is exponential, climb(0) calls climb(1) and climb(2), each of which calls two more, and so on. For n=40, this is roughly 2^40 calls. Crucially, the same subproblems are recomputed many times: climb(3) is computed once from climb(1) and again from climb(2).

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

What are the base cases, and what does each step depend on from earlier steps?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.