題目要求
假設(shè)你正在爬樓梯古程。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個臺階喊崖。你有多少種不同的方法可以爬到樓頂呢挣磨？
注意：給定 n 是一個正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂荤懂。
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂茁裙。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
思路一
遞歸的解法，設(shè)有n階樓梯(n>0)节仿，那么當(dāng)爬到第n階樓梯時晤锥，有2種方式，要么是爬1階到n階廊宪，要么爬2階到n階矾瘾，若求階公式為f(n)，則f(n) = f(n-1) + f(n-2)箭启，終止條件是n==1 return 1, n==2 return 2
→_→ talk is cheap, show me the code
# 直接使用遞歸會AC超時壕翩，這里使用一個dict保存中間結(jié)果復(fù)用，勉強(qiáng)通過
d = dict()
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if not n:
return 0
if n == 1 or n == 2:
return n
if d.get(n):
return d.get(n)
res = self.climbStairs(n-1) + self.climbStairs(n-2)
d[n] = res
return res
思路二
遞歸的思想是從后往前傅寡，遞過去歸回來放妈；我們找到了遞歸公式北救，也就能寫出非遞歸的實(shí)現(xiàn)方式，當(dāng)ｎ=1時芜抒，有１中走法扭倾，當(dāng)ｎ＝２時，有２種走法挽绩；有了這兩個基礎(chǔ)膛壹，就可以求出ｎ＝３時，有f(n-1) + f(n-2) =3種走法唉堪；（也就是斐波那契數(shù)列）
→_→ talk is cheap, show me the code
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if not n:
return 0
if n == 1 or n == 2:
return n
pre = 2
prepre = 1
ret = 0
for i in range(3, n+1):
ret = pre + prepre
prepre = pre
pre = ret
return ret
