# Python different solutions (bottom up, top down).

• ``````# 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]``````

• the first method does not pass due to the time limit

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

• Why does the last method outperform the first one?

• @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.

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