Back to ChallengesClimbing StairsEasy 15 min

Climbing Stairs

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 = 2

Output: 2

There are two ways: 1 step + 1 step, or 2 steps.

Input: n = 3

Output: 3

Three ways: 1+1+1, 1+2, or 2+1.

Constraints

• 1 <= n <= 45

Complexity Analysis

Time

O(n)

one pass to calculate states.

Space

O(1)

constant storage space using two variables.

Test Cases

#1 One stair

Input: 1

Expected: 1

#2 Two stairs

Input: 2

Expected: 2

#3 Three stairs

Input: 3

Expected: 3

#4 Five stairs

Input: 5

Expected: 8

#5 Ten stairs

Input: 10

Expected: 89

JavaScript

Output

Click "Run Code" to see output here...