Climbing stairs

Problem Count the distinct ways to climb a staircase of n steps if each move climbs 1 or 2 steps.

Input / Output

• Input: integer n.
• Output: the number of distinct step sequences reaching step n.

Constraints

• 1 <= n <= 45 (fits in int; the answer is Fibonacci-sized).

Example

• n = 3 -> 3 ([1,1,1], [1,2], [2,1])
• n = 4 -> 5