---

---

70. 爬樓梯：

假設你正在爬樓梯。需要 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 階

提示：

• 1 <= n <= 45

---

分析：

• 面對這道算法題目，二當家的再次陷入了沉思。
• 可以爬一階或者兩階臺階，那也就是說，除了初始位置，和第一階臺階，到達其他階臺階 n 的方式，就只能從 n - 1 階臺階，或者 n - 2 階臺階來。
• 這是典型的動態規劃，到初始位置和第一階臺階的方式只有一種，之后到達每一階臺階的發方法總數都可以動態計算得來，即 f(x) = f(x ? 1) + f(x ? 2)。
• 動態規劃方法我覺得很好了，但是由于有規律，用數學的方式計算，當然更快了，另外將前幾項列出來，再結合定義，就會發現，到達每一階臺階的方法總數恰好就是 斐波那契數列。
• 動態規劃只能從 1 到 n 按順序推算，在 n 較大時，效率仍不令人滿意，矩陣快速冪，可以有像二分查找一樣的效率，數學的知識都還給老師了，有興趣的可以去研究一下，能看明白，但是過段時間又會忘記，無奈啊，矩陣快速冪 是 矩陣乘法 和 快速冪 的結合，可以先分別了解，再結合理解。
• 所以建議一定要把動態規劃優先掌握，其次是快速冪，至于通項公式，數學的方法，很難舉一反三，要具體問題具體分析，說到底還是需要掌握數學知識本身，與君共勉。
• 最后，爬樓梯當然要5階5階的上才霸氣。

---

題解：

rust：

impl Solution {pub fn climb_stairs(n: i32) -> i32 {let sqrt5 = 5f64.sqrt();let fibn = ((1f64 + sqrt5) / 2f64).powi(n + 1) - ((1f64 - sqrt5) / 2f64).powi(n + 1);return (fibn / sqrt5).round() as i32;}
}

---

go：

func climbStairs(n int) int {sqrt5 := math.Sqrt(5)pow1 := math.Pow((1+sqrt5)/2, float64(n+1))pow2 := math.Pow((1-sqrt5)/2, float64(n+1))return int(math.Round((pow1 - pow2) / sqrt5))
}

---

c++：

class Solution {
public:int climbStairs(int n) {const double sqrt5 = sqrt(5);const double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);return (int) round(fibn / sqrt5);}
};

---

python：

class Solution:def climbStairs(self, n: int) -> int:sqrt5 = math.sqrt(5)fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1)return round(fibn / sqrt5)

---

java：

class Solution {public int climbStairs(int n) {final double sqrt5 = Math.sqrt(5);final double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);return (int) Math.round(fibn / sqrt5);}
}

---

非常感謝你閱讀本文~
歡迎【點贊】【收藏】【評論】三連走一波~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子：https://le-yi.blog.csdn.net/ 博客原創~

---