How many ways up the stairs

You are climbing a staircase of n steps. Each move takes you up either one step or two. How many different ways are there to reach the top?

Worked example#

For n = 4:

Five ways.

Listing them stops being possible very quickly, so look at it differently. The last move onto step 4 was either a single step from step 3, or a double step from step 2. Nothing else can reach step 4. So:

ways(4) = ways(3) + ways(2)

That holds for every step, which gives a table you can fill in order:

Those are the Fibonacci numbers, which is a nice surprise and not something you need to notice to solve it.

Why writing it recursively is a trap#

ways(n) = ways(n - 1) + ways(n - 2) written directly as a recursive function is correct and unusably slow. ways(40) recomputes ways(38) twice, ways(37) three times, and so on: the work doubles with every step, so it is O(2^n).

The fix is not a cleverer formula. It is to compute each answer once and keep it. Filling the table upward does that naturally, and it is the whole idea behind dynamic programming: the same subproblems keep reappearing, so solve each one once.

Only two numbers needed#

Each row reads the two before it, so the whole table is unnecessary:

oneBack = 1   # ways to reach step 1
twoBack = 1   # ways to reach step 0, meaning already there
for step from 2 to n:
    current = oneBack + twoBack
    twoBack = oneBack
    oneBack = current

Time O(n), memory O(1).

Constraints#

• 1 <= n <= 45
• The answer fits in a 64 bit integer