Climbing Stairs
EasyDynamic Programming · NVIDIA
You are at the bottom of a staircase with n steps. In one move you can climb either 1 step or 2 steps.
Return the number of distinct sequences of moves that take you exactly to the top step. Two sequences are different if they differ in at least one move or in the order of moves (so 1, 2 and 2, 1 are different).
Example 1
- Input:
- n = 4
- Output:
- 5
- Explanation
- The five sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Example 2
- Input:
- n = 1
- Output:
- 1
- Explanation
- With one step, the only option is a single 1-step move.
Example 3
- Input:
- n = 6
- Output:
- 13
- Explanation
- The last move is either a 1 from step 5 or a 2 from step 4, so the count is ways(5) + ways(4) = 8 + 5 = 13.
Constraints
- 1 ≤
n≤ 45