假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2

輸出：2

解釋?zhuān)河袃煞N方法可以爬到樓頂。

1\. 1 階 + 1 階

2\. 2 階

示例 2：

輸入：n = 3

輸出：3

解釋?zhuān)河腥N方法可以爬到樓頂。

1\. 1 階 + 1 階 + 1 階

2\. 1 階 + 2 階

3\. 2 階 + 1 階

來(lái)源：力扣（LeetCode）

鏈接：https://leetcode.cn/problems/climbing-stairs

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。''

公式
      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

運(yùn)行超時(shí)

///  增加mapDict 減少重復(fù)計(jì)算

    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