A hill temple has a long stone staircase with n steps. Meera stands at the bottom. She wants to reach the top step.
In each move she climbs one step or two steps. Count the different ways she can reach the top. Two ways are different when their moves are different.
Examples
Example 1:
Input: n = 4
Output: 5
Explanation: The five ways are 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1 and 2 + 2.
Example 2:
Input: n = 7
Output: 21
Explanation: For 1, 2, 3, 4, 5, 6, 7 steps the number of ways is 1, 2, 3, 5, 8, 13, 21. Each number is the sum of the two before it. The last move is either 1 step or 2 steps.
Example 3:
Input: n = 9
Output: 55
Explanation: Continue the same pattern: 21, 34, 55 for 7, 8, 9 steps.