58. Climbing Stairs

Easy · Dynamic Programming

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?

For example, if there are 3 steps, you can reach the top by: (1) taking one step at a time (1+1+1), (2) taking one step, then two steps (1+2), (3) taking two steps, then one step (2+1). That's 3 distinct ways.

Return the total number of distinct ways to climb the staircase.

Examples

Example 1
Input: n = 2
Output: 2
Explanation: There are 2 ways: (1) 1 step + 1 step, (2) 2 steps.
Example 2
Input: n = 3
Output: 3
Explanation: There are 3 ways: (1) 1+1+1, (2) 1+2, (3) 2+1.

Constraints