假設(shè)你正在爬樓梯鸦致。需要 n 階你才能到達(dá)樓頂棕诵。
每次你可以爬 1 或 2 個臺階纪蜒。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數(shù)扰付。
爬樓梯問題的實質(zhì)就是 斐波那契數(shù)列
f(n) = f(n-1) + f(n-2)
遞歸實現(xiàn)
最先想到的就是簡單粗暴的遞歸方式實現(xiàn).
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if(n == 1 or n == 0):
return 1
else:
# 假如不是以類的形式, 直接 return 函數(shù)() 不需要加 self.
return self.climbStairs(n-1) + self.climbStairs(n-2)
顯然這種方式是無法通過 LeeCode 測試的, 絕對超時. 就算不超時換個大一點的數(shù)也會棧溢出.
關(guān)于 Python 的尾遞歸方式實現(xiàn)可以參考廖雪峰老師的文章 - 遞歸函數(shù)
非遞歸實現(xiàn)
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if(n == 1 or n == 0):
return 1
temp = [1, 1]
result = 0
while(n > 1):
result = temp[-1] + temp[-2]
temp[-1] = temp[-2]
temp[-2] = result
n = n - 1
return result
