70. 爬樓梯：

假設(shè)你正在爬樓梯。需要 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 階臺階來。
• 這是典型的動態(tài)規(guī)劃，到初始位置和第一階臺階的方式只有一種，之后到達每一階臺階的方法總數(shù)都可以動態(tài)計算得來，即 f(x) = f(x ? 1) + f(x ? 2)。
• 動態(tài)規(guī)劃方法我覺得很好了，但是由于有規(guī)律，用數(shù)學的方式計算，當然更快了，另外將前幾項列出來，再結(jié)合定義，就會發(fā)現(xiàn)，到達每一階臺階的方法總數(shù)恰好就是 斐波那契數(shù)列。
• 動態(tài)規(guī)劃只能從 1 到 n 按順序推算，在 n 較大時，效率仍不令人滿意，矩陣快速冪，可以有像二分查找一樣的效率，數(shù)學的知識都還給老師了，有興趣的可以去研究一下，能看明白，但是過段時間又會忘記，無奈啊，矩陣快速冪 是 矩陣乘法 和 快速冪 的結(jié)合，可以先分別了解，再結(jié)合理解。
• 所以建議一定要把動態(tài)規(guī)劃優(yōu)先掌握，其次是快速冪，至于通項公式，數(shù)學的方法，很難舉一反三，要具體問題具體分析，說到底還是需要掌握數(shù)學知識本身，與君共勉。
• 最后，爬樓梯當然要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/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-650450.html

到了這里，關(guān)于算法leetcode｜70. 爬樓梯（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！