Climbing Stairs

You get an integer n, the number of steps in a staircase. Each move takes you up 1 step or 2 steps.

Return how many different ways you can climb from the bottom to exactly the top.

The order of the moves matters. For example, 1 + 2 and 2 + 1 are two different ways.

Example 1:

Input: n = 4
Output: 5
Explanation: The five ways are:
1. 1 + 1 + 1 + 1
2. 1 + 1 + 2
3. 1 + 2 + 1
4. 2 + 1 + 1
5. 2 + 2

Example 2:

Input: n = 1
Output: 1
Explanation: One move of 1 step is the only way.

Example 3:

Input: n = 6
Output: 13
Explanation: Group the ways by how many 2s they use:
no 2s: 1 way (1 + 1 + 1 + 1 + 1 + 1),
one 2: 5 ways (2 + 1 + 1 + 1 + 1 in any order),
two 2s: 6 ways (2 + 2 + 1 + 1 in any order),
three 2s: 1 way (2 + 2 + 2).
In total, 1 + 5 + 6 + 1 = 13.

Constraints:

• n is from 1 to 45.
• The answer fits in a 32-bit signed integer.
• For n = 45, the answer is 1,836,311,903.