Climbing Stairs
You are climbing a staircase with n steps. Each time you can climb either 1 or 2 steps. Return the number of distinct ways to reach the top.
Two ways are distinct if the sequence of moves differs, so climbing 1 then 2 is not the same as climbing 2 then 1.
Input & Output
Input
n — the number of steps in the staircase
Output
the number of distinct ways to climb to the top
Example
Input
n = 2
Output
2
Explanation
Two sequences reach the top: (1 + 1) and (2).
Example
Input
n = 5
Output
8
Explanation
The eight sequences are (1+1+1+1+1), (1+1+1+2), (1+1+2+1), (1+2+1+1), (2+1+1+1), (1+2+2), (2+1+2), and (2+2+1).
Constraints
1 <= n <= 50