Climbing stairs leetcode problem

Hi forks , In this blog I will be going through on of the most asked problem in the interview i.e Climbing Stairs .

Photo by Ruffa Jane Reyes on Unsplash

Question :

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?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

I recommend you guys to just go through the question first and try to solve this question in leetcode and for hints, you can scroll down.

Climbing Stairs - LeetCode

Solution Idea: There are n steps, you can either go one step at a time or two steps right. If you design the recurrence relation for this question it would be

T(n) = T(n-1) + T(n-2)

T(2) = T(1) + T(0) = 1 + 0 = 1

The base case would be if (n ==1 || n==0) then no of ways would be 1 and another case would be if(n < 0) no of ways would be zero.

Let’s solve this question with the basic recursion solution.

Here, If you see it clearly it takes O(2 ^ n ) time to calculate the no of ways to climb the staircase.

Let’s apply Recursive DP to optimize this solution to O(n).

Here above, I have added a solution for iterative DP also. In DP, just we need to check, how many variables are dynamic/Changing. Here we clearly see one variable i.e n is dynamic throughout the code. So we need to take one dimensional Array to store the results for reaching each step.

As we already know, for reaching 0 & 1 step there is only one way so,

mem[0] = 1 , mem[1] = 1

Now we know for reaching 2 steps either we can take 1 step or 2 steps directly.

mem[2] = mem[2–1] + mem[2–2] = mem[1] + mem[0] = 1 + 1 = 2 ways.

In that way, we can loop through the n elements and mem[n] would be the answer finally.

I hope you would have got a clear idea about the question and all three solutions. Reading not stops here, You can go through the uber interview experience here.

Thanks Guys , for reading this blog and give a clap if you liked the blog and if you have any questions , you can comment on this blog , I will happy to help you.