Build on dynamic programming concepts to efficiently solve complex optimization problems.

Coding

Solves complex problems by breaking them into smaller overlapping subproblems and storing results to avoid redundant computations, optimizing time and space.

Dynamic Programming

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

#
## 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$ 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.

### Optimized solution using dynamic programming pattern
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:

Let's solve the Climbing Stairs problem using the Dynamic Programming pattern.

Solution: Climbing Stairs

Statement▼

Solution

Naive approach

Solution: Climbing Stairs

Statement▼

Solution

Naive approach