假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階泰偿。你有多少種不同的方法可以爬到樓頂呢？
示例 1：
輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂欠母。
1\. 1 階 + 1 階
2\. 2 階
示例 2：
輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1\. 1 階 + 1 階 + 1 階
2\. 1 階 + 2 階
3\. 2 階 + 1 階
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/climbing-stairs
著作權(quán)歸領(lǐng)扣網(wǎng)絡所有吆寨。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)赏淌，非商業(yè)轉(zhuǎn)載請注明出處。''
公式
n = 1 1
f(n) n = 2 2
f(n-1)+f(n-2) >3
/// 遞歸解法
func climbStairs(_ n: Int) -> Int {
if n == 1 {return 1}
if n == 2 {return 2}
return climbStairs(n-1)+climbStairs(n-2)
}
image.png
運行超時
/// 增加mapDict 減少重復計算
var mapDict = Dictionary<Int, Int>()
func climbStairs1(_ n: Int) -> Int {
if n == 1 {return 1}
if n == 2 {return 2}
if mapDict[n] == nil {
let result = climbStairs1(n-1)+climbStairs1(n-2)
mapDict[n] = result
}
return mapDict[n] ?? 0
}
image.png
