Climbing Stairs

Problem

A staircase has n steps. You start on the ground (step 0) and on each move you may go up either one step or two steps. Count the number of distinct move sequences that land you exactly on step n. Two sequences are different if the list of step sizes differs, so 1,2 and 2,1 are counted separately.

• n is a positive integer no larger than 60.
• Return the exact count as an integer; it fits comfortably in 64 bits for this range.

Examples

• n = 4 → 5. The sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2.
• n = 6 → 13. Every sequence either ends with a 1-step from step 5 (8 ways) or a 2-step from step 4 (5 ways).
• n = 1 → 1. Only a single 1-step reaches the top.

Hints

1. Think about the very last move you make before arriving on step n. Where must you have been standing?
2. If you knew how many ways there are to reach step n-1 and step n-2, could you combine those numbers without recounting anything?
3. This is a one-dimensional DP whose recurrence is the Fibonacci relation; you only ever need the two most recent values.