Climbing Stairs
Easy · dynamic programming
A staircase has n steps and you start on the ground, before the first step. On every move you climb either 1 step or 2 steps.
Return the number of distinct sequences of moves that take you exactly to the top. Two sequences are different if they differ in at least one move, so 1 + 2 and 2 + 1 count as two.
Examples
Example 1
Input: n = 2
Output: 2
Two ways: 1 + 1, or a single 2.
Example 2
Input: n = 4
Output: 5
1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Example 3
Input: n = 1
Output: 1
Constraints
- 1 <= n <= 45
- The answer always fits in a 32-bit signed integer.