Count Ways To Reach the nth stair 🤷🏻‍♀️ (Climbing 🧗🏼‍♂️ Stairs)| Python & CPP | DP | Coding Interview

This fundamental problem can show the use of DP in very simple terms. We will easily see why and how to implement a DP solution in this case. This problem has been asked by Amazon, Microsoft, Google, Bloomberg, Apple, and Adobe.

Climbing stairs problem

After discussing the brute force (recursive way), we will discuss both the bottom-up approach as well as a top-down approach.

This article belongs to the 30 Days Preparation Plan.

Contents

1. Description
2. Brute Force (Recursive)
3. Solution (Top-down approach)
4. Solution (Bottom-up approach)
5. Time & Space Complexity

Description

We are climbing 🧗‍♂️ a staircase, and it takes n steps to reach the top. Give the number of ways we can reach the top if we can either climb 1 step or 2 steps.

Let’s say we have to climb 2 stairs in total; then we can get there by taking 2 one steps or by taking 1 two-step.