You are given an integer N representing the number of stairs. You can climb either 1 step or 2 steps at a time. Your task is to count the total number of different ways to reach exactly the Nth stair.
Calculate and return the total number of possible ways.
Example 1
Input: N = 5
Output: 8
Explanation: The possible ways 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).
Example 2
Input: N = 6
Output: 13
Explanation: The possible ways are (1+1+1+1+1+1), (1+1+1+1+2), (1+1+1+2+1), (1+1+2+1+1), (1+2+1+1+1), (2+1+1+1+1), (1+1+2+2), (1+2+1+2), (1+2+2+1), (2+1+1+2), (2+1+2+1), (2+2+1+1), and (2+2+2).
Example 3
Input: N = 4
Output: 5
Explanation: The possible ways are (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), and (2+2).
Sign in to write, run, and submit your solution against the full test suite.