Solution: Climbing Stairs

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?

Constraints:

• $1 \leq$ n $\leq 45$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

Naive approach

A naive approach to solve this problem would be to find all the possible ways to climb the stairs. Given that you can only climb either $1$ or $2$ steps at a time, we can say that the number of ways to climb $n$ stairs is the sum of the following:

• the number of ways to reach the $(n−1)^{th}$ stair, since we can then climb $1$

...