Climbing Stairs

Easy~15 min

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

Example 1
Input: n = 2
Output: 2
Explanation: There are two ways: (1) 1 step + 1 step, (2) 2 steps.
Example 2
Input: n = 3
Output: 3
Explanation: There are three ways: (1) 1+1+1, (2) 1+2, (3) 2+1.
Example 3
Input: n = 5
Output: 8
Explanation: The number of ways follows the Fibonacci sequence: 1, 2, 3, 5, 8.

Constraints

  • 1 <= n <= 45
  • Expected time complexity: O(n)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run