題目
假設(shè)你正在爬樓梯布隔。需要 n 階你才能到達(dá)樓頂离陶。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢衅檀？
注意：給定 n 是一個正整數(shù)招刨。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂哀军。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
解題思路
這一題一開始我竟然考慮排列組合沉眶，由于數(shù)學(xué)丟了一些年打却，導(dǎo)致我又去翻公式，折騰了半天谎倔，還是一籌莫展柳击。
然后看了一下提示，說是考慮之前的步數(shù)片习，才恍然大悟可用遞歸捌肴。
因為，如果當(dāng)已經(jīng)爬了n層了藕咏，用了m種方法状知，如果只能在這個現(xiàn)狀的基礎(chǔ)上，再走一步孽查，那么饥悴，此時只有m種可能性，即只能走一步盲再；
那是不是說西设，爬n + 1層，就有2m種可能性呢答朋？
并不是這樣贷揽，因為上面說的情況是，走了n層以后現(xiàn)狀梦碗，即上一步不能改變了擒滑，但是，當(dāng)爬了n-1層的時候叉弦，如果后面還有2層可以走，那么除了爬1階以外藻糖，還可以有2階這個選項淹冰。
那么，假設(shè)爬n-1層的時候巨柒，有o種可能性了樱拴，然后下一步爬2階，即可到n+1洋满。
因此晶乔，爬n+1層的可能性是 m + o
也就是說：
此外，不能寫單純的遞歸式牺勾，會導(dǎo)致大量的重復(fù)計算正罢，這里用一個字典來儲存計算結(jié)果，可減少計算次數(shù)驻民。
答案
class Solution(object):
def __init__(self):
self.n_dict = {}
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n in self.n_dict:
return self.n_dict[n]
if n == 1:
return 1
if n == 2:
return 2
result = self.climbStairs(n - 2) + self.climbStairs(n - 1)
self.n_dict[n] = result
return result
