# Top down  TLE
def climbStairs1(self, n):
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n1)+self.climbStairs(n2)
# 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[i1] + res[i2]
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(n1, dic)
def helper(self, n, dic):
if dic[n] < 0:
dic[n] = self.helper(n1, dic)+self.helper(n2, 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(n1) + self.climbStairs(n2)
return self.dic[n]
Python different solutions (bottom up, top down).


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