Python different solutions (bottom up, top down).


  • 24
    C
    # Top down - TLE
    def climbStairs1(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n-1)+self.climbStairs(n-2)
     
    # Bottom up, O(n) space
    def climbStairs2(self, n):
        if n == 1:
            return 1
        res = [0 for i in xrange(n)]
        res[0], res[1] = 1, 2
        for i in xrange(2, n):
            res[i] = res[i-1] + res[i-2]
        return res[-1]
    
    # Bottom up, constant space
    def climbStairs3(self, n):
        if n == 1:
            return 1
        a, b = 1, 2
        for i in xrange(2, n):
            tmp = b
            b = a+b
            a = tmp
        return b
        
    # Top down + memorization (list)
    def climbStairs4(self, n):
        if n == 1:
            return 1
        dic = [-1 for i in xrange(n)]
        dic[0], dic[1] = 1, 2
        return self.helper(n-1, dic)
        
    def helper(self, n, dic):
        if dic[n] < 0:
            dic[n] = self.helper(n-1, dic)+self.helper(n-2, dic)
        return dic[n]
        
    # Top down + memorization (dictionary)  
    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]

  • 6
    S

    the first method does not pass due to the time limit


  • 0
    S

    I think the first solution always cause TLE. Because the time complexity is O(2^n).


  • 0
    D

    Why does the last method outperform the first one?


  • 0
    K

    @Dylan.Qiu
    It's because the last method memorizes the results of the subproblems via a dict when it first encounters, and thus duplicate subproblems are not recomputed. Therefore it outperforms the first method.


Log in to reply
 

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