# leetcode 70 Climbing Stairs (爬樓梯) python3 多種思路(Top down / Bottom up)

``````class Solution:
# def __init__(self):
#         self.dic = {1:1, 2:2}
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
# 這道題本質上是一個斐波那契數列,因為後一個數總是等於前兩個數字之和!
# 思路一:  Top down - TLE  因為前面已經算過的數字不能直接呼叫,總是需要重新計算.
# if n == 1:
#     return 1
# if n == 2:
#     return 2
# if n > 2:
#     return self.climbStairs(n-1)   self.climbStairs(n-2)
# 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)  對於思路一的改進,用一個字典來儲存前面計算過的部分,減少運算時間
# if n not in self.dic:
#     self.dic[n] = self.climbStairs(n-1)   self.climbStairs(n-2)
# return self.dic[n]
# Bottom up, O(n) space  思路二:自底向上. 儲存前面計算過的數字,用空間來換取時間
# if n == 1:
#     return 1
# res = [0 for i in range(n)]
# res[0], res[1] = 1, 2
# for i in range(2, n):
#     res[i] = res[i-1]   res[i-2]
# return res[-1]
# Bottom up, O(n) space  思路二:自底向上. 進一步壓縮佔用的儲存空間
if n == 1:
return 1
a, b = 1, 2
for i in range(2, n):
a,b = b,a b
return b``````