Climbing Stairs

Problem Statement

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?

Approach

This is a Fibonacci-like problem. The number of ways to reach step n is the sum of ways to reach step n-1 and n-2.

Complexity Analysis

Examples

Example 1

Input: n = 2 Output: 2 Explanation: 1. 1 step + 1 step, 2. 2 steps

Example 2

Input: n = 3 Output: 3 Explanation: 1. 1+1+1, 2. 1+2, 3. 2+1

Constraints

• ▸1 <= n <= 45

Sign in to run your code...