Disclaimer

The views and opinions expressed in this blog and the accompanying codes are solely those of the author and do not represent the views or opinions of the author's employer. The author does not receive any compensation for creating any content published here. The author created this blog and the accompanying codes on the author's own time, using the author's own resources.

Today, I have stumbled upon one very easy yet interesting problem, it really related to our day-to-day job, who doesn't climb stairs now a then, huh?

I love to solve problems in leetcode, and today's problem was - leetcode.com/problems/climbing-stairs

Let me put the questions here -

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

It's a very easy problem if you think about your house's staircase, if you remember the Fibonacci series, it is the same type of problem here.

Let me put a link here on how to solve a Fibonacci series using recursion - geeksforgeeks.org/python-program-for-progra..

If you have gone through the above explanation and thought that this problem pattern is very similar that's correct I thought the same.

Now take a deeper look at the below solution -

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

We have a base case of n: 1 and 2 and then the rest is taken care of by the recursion. This was my first solution in leetcode. It passed the initial test cases and then boooom!!!! It failed due to the time limit exceeded when n is a large value like n > 40.

So what I learnt is, this recursive approach is not very efficient, because it can take a long time to calculate the result for large values of n. This is because each time the function is called, it has to recalculate the result for all the intermediate values of n, which can be very slow. This is why I was getting a time limit exceeded error for n = 38 because the function takes too long to calculate the result for this value of n.

One way to make the climbStairs() function more efficient is to use dynamic programming, wait what is DP !! let's see what is dynamic programming(DP) from top institutes of the world -

Stanford - web.stanford.edu/class/cs97si/04-dynamic-pr..

MIT - ocw.mit.edu/courses/6-006-introduction-to-a..

Harvard - people.seas.harvard.edu/~cs125/fall16/lec5...

we can use dynamic programming to avoid recalculating the same values multiple times. In dynamic programming, you store the results of previous calculations in a data structure (such as a dictionary), so that you can look them up later without having to recalculate them. This can save a lot of time.

So let's a look at the final optimized solution with dynamic programming -

def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        stairs = [0] * (n + 1)

        stairs[1] = 1
        stairs[2] = 2

        for i in range(3, n + 1):
            stairs[i] = stairsi - 1] + stairs[i - 2]

        return stairs[n]

Explanation -

The climbStairs() function is a solution to the problem of climbing a staircase that takes n steps to reach the top. The function uses a dynamic programming approach to solve the problem, by storing the results of previous calculations in an array stairs.

The function first checks if the number of steps n is less than or equal to 2. If this is the case, it returns n immediately, because there is only one way to climb a staircase with 1 or 2 steps (either by taking 1 step at a time, or by taking 2 steps at a time).

Next, the function initializes an array stairs with n + 1 elements, and sets the first two elements of the array (stairs[1] and stairs[2]) to 1 and 2, respectively. This is because there is only one way to climb a staircase with 1 step (by taking 1 step at a time), and there are two ways to climb a staircase with 2 steps (by taking 1 step at a time twice, or by taking 2 steps at a time).

The function then enters a for loop, which iterates over the range of numbers from 3 to n + 1. For each number i in this range, the function sets the i-th element of the stairs array (stairs[i]) to the sum of the previous two elements of the stairs array (stairs[i - 1] and stairs[i - 2]). This is because the number of ways to climb a staircase with i steps is equal to the number of ways to climb a staircase with i - 1 steps plus the number of ways to climb a staircase with i - 2 steps.

Finally, the function returns the last element of the stairs array (stairs[n]), which is the number of ways to climb a staircase with.

Hope you enjoyed this blog.