Climbing Ten Stairs

Question

You climb a staircase of 10 steps, taking either 1 or 2 steps at a time. How many distinct ways can you reach the top?

Accepted Answer

Let f(n) count climbs of n stairs. The last move was a 1-step (from stair n-1) or a 2-step (from stair n-2), and these cases are disjoint and exhaustive: f(n) = f(n-1) + f(n-2), qquad f(1) = 1,; f(2) = 2. Roll forward: 1, 2, 3, 5, 8, 13, 21, 34, 55, mathbf89. Fibonacci again. Approach 2, sum over the number of 2-steps With k two-steps you make 10 - k moves total; choose which are the 2-steps: sum_k=0^5 binom10-kk = 1 + 9 + 28 + 35 + 15 + 1 = 89. checkmark This is the same Fibonacci skeleton as "binary strings with no two adjacent 1s", different costume, identical recurrence. Recognizing the shape (linear recurrence from classify-by-last-move) is the transferable skill; the interviewer follow-up is usually a tweak that tests whether you re-derive rather than recite.

Climbing Ten Stairs

Problem

Your answer

Hints

More Combinatorics to train on