Distinct way to reach top of Stairs | Climbing Stairs Top-Down Approach-CodePudding

Problem :
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?

Input: n = 3

Output: 3

Explanation: There are three ways to climb to the top.

1 step 1 step 1 step
1 step 2 steps
2 steps 1 step

Here is my 2 different approach for this Problem.

Approach 1:

Class Solution: 
    def climbStairs(self, n):
        dic = {1:1, 2:2}
        if n not in dic:
            dic[n] = self.climbStairs(n-1)   self.climbStairs(n-2)
        return dic[n]

Approach 2:

Class Solution:
    def __init__(self):
        self.dic = {1:1, 2:2}
    
    def climbStairs(self, n):
        if n not in self.dic:
            self.dic[n] = self.climbStairs(n-1)   self.climbStairs(n-2)
        return self.dic[n]

Now the problem is whenever n goes beyond 36 I get time limit exceeded from Approach 1 but Approach 2 works perfectly fine.

I'm solving this problem on leetcode. Even I tried to run this on VS code but execution is very very slow from n > 40.

I'm not understanding what impact does dictionary inside constructor makes in making execution faster.

CodePudding user response：

The first line in approach 1 creates a new dictionary {1: 1, 2: 2} with each call. If you wanted to use a shared dictionary, you would have to pass it as an argument to the function or have it as an instance variable like you do in approach 2.

This is how you can share the dictionary and pass it every time as an argument:

class Solution: 
    def climbStairs(self, n, dic=None):
        # if this is the first call, create the dictionary
        if dic is None:
            dic = {1: 1, 2: 2}
        if n not in dic:
            dic[n] = self.climbStairs(n-1, dic)   self.climbStairs(n-2, dic)
        return dic[n]

CodePudding user response：

Approach 2 passes because it uses a technique called memoization. In the first approach, if you carefully check which functions calls are made, you quickly figure out that there are overlapping problems and it leads to O(2^n) solution, while with memoization it's only O(n).

In the first approach you rewrite dict on every function call, probably this is not what you want. You can move it to the class level, like so:

class Solution:
    dic = {1: 1, 2: 2}

    def climbStairs(self, n):
        if n not in self.dic:
            self.dic[n] = self.climbStairs(n - 1)   self.climbStairs(n - 2)
        return self.dic[n]