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$

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.

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$ step to reach the $n^{th}$ stair
• the number of ways to reach the $(n−2)^{th}$ stair, since we can then climb $2$ step to reach the $n^{th}$ stair

We can now formulate our recursive algorithm to count the number of ways to climb $n$ stairs:

• Base case 1: if $n = 1$, there is only one way to reach the $1^{st}$ stair, which is by climbing $1$ step. Therefore, we return $1$.
• Base case 2: if $n = 2$, the total number of ways to reach the $2^{nd}$ stair is $2$ either by climbing $2$ steps directly or taking $1$ step two times. Therefore, we return $2$.
• Recursive case: The total number of ways that we can climb the stairs is climb_stairs(n-1) + climb_stairs(n-2)

The algorithm is based on recursion, which can potentially lead to a lot of redundant calculations. For example, when you calculate climb_stairs(n-1), it also recursively calculates climb_stairs(n-2), and when you calculate climb_stairs(n-2), it recalculates climb_stairs(n-3), and so on. This results in an exponential number of redundant calculations, making the algorithm very inefficient.

We will use the bottom-up technique to solve this problem and to avoid redundant calculations. The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic problems. We break the problem into subproblems. The optimal substructure property is being used, i.e., the optimal solution can be constructed efficiently from the optimal solutions of its subproblems. In this approach, the smallest problem is solved, the result is saved, and larger subproblems are computed based on the evaluated results.

We know that the:

• total number of ways to reach the $1^{st}$ stair is $1$ by climbing $1$ step.
• total number of ways to reach the $2^{nd}$ stair is $2$ either by climbing $2$ steps directly or taking $1$ step two times.

Therefore, we will populate the lookup_table with these values.

The total number of ways to reach the $n^{th}$ stair would be equal to the sum of the following:

• the number of ways to reach the $(n-1)^{th}$ stair
• the number of ways to reach the $(n-2)^{th}$ stair

That is, we simply sum up the ways to reach the previous two stairs. The $n^{th}$ index of the lookup_table then stores the required value.

Let’s look at the following illustration to get a better understanding of the solution: