Description
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Examples
Input:
n = 2Output:
2Explanation:
There are two ways: 1. 1 step + 1 step, 2. 2 steps
Input:
n = 3Output:
3Explanation:
There are three ways: 1. 1 step + 1 step + 1 step, 2. 1 step + 2 steps, 3. 2 steps + 1 step
Input:
n = 4Output:
5Explanation:
There are five ways to reach step 4: 1. 1+1+1+1 steps, 2. 1+1+2 steps, 3. 1+2+1 steps, 4. 2+1+1 steps, 5. 2+2 steps
Constraints
- •
1 ≤ n ≤ 45