All DSA problems
EasyDynamic ProgrammingAmazonGoogleAdobe
Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can climb either **1 or 2** steps. In how many distinct ways can you climb to the top?
Print the number of ways.
**Input:** single integer n
Examples
Example 1
Input:
2
Output: 2
1+1 or 2
Example 2
Input:
3
Output: 3
1+1+1, 1+2, 2+1
Constraints
- 1 ≤ n ≤ 45
Target: O(n) time · O(1) space