A staircase has n steps and you start at the bottom. A move takes you up either 1 step or 2 steps. Count the sequences of moves that end exactly on step n.
The order of the moves matters: 1 then 2 is a different sequence from 2 then 1.
Example 1
Input
n = 4
Output
5
Explanation
the sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Example 2
Input
n = 1
Output
1
Explanation
only one move is possible, a single step.
Constraints:
1 <= n <= 45, so the answer always fits in a 32-bit signed integer
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.