My O(n) solution in python (DP (Recursion with Memoization))


  • 0
    S
    def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            res=[0]*(n+1)
            return self.climb_with_dp(n,res)
        def climb_with_dp(self,n,res):
            if n==0:
                res[0]=1
            if n==1:
                res[1]=1
            elif res[n]==0:
                res[n]=self.climb_with_dp(n-1,res)+self.climb_with_dp(n-2,res) #recursion with memoization
            return res[n]   
    

  • 0
    T

    Why is this not O(n)? You are still calculating every value from res[0] to res[n] once right?


  • 1
    S

    @tapegram Sorry My bad thanks for correcting it. It will still be O(n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.