每日一道 LeetCode (17)：爬樓梯
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：爬樓梯
題目來源：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入：2
輸出：2
解釋：?有兩種方法可以爬到樓頂。
1.??1?階?+?1?階
2.??2?階
示例 2：
輸入：3
輸出：3
解釋：?有三種方法可以爬到樓頂。
1.??1?階?+?1?階?+?1?階
2.??1?階?+?2?階
3.??2?階?+?1?階
解題過程
過程啥過程，這道題完全沒有頭緒好么。
好不容下班后爬了個(gè) 7 層樓回家，結(jié)果打開電腦接著讓我爬樓梯，爬個(gè)錘子哦。
最近的題是怎么了，明明說好了是簡單難度，結(jié)果還是一眼看下去連想法都沒，讓我回歸下前兩天的那些題它不好么。這道題我有一種強(qiáng)烈的預(yù)感是一道數(shù)學(xué)題，和程序關(guān)系不是很大。
么得辦法，不會(huì)做就只能打開答案開始看答案了。
解題方案一：動(dòng)態(tài)規(guī)劃
說是動(dòng)態(tài)規(guī)劃，實(shí)際上是對題做了一個(gè)簡單的推演：
輸入????輸出
1???????1
2???????2
3???????3
4???????5
5???????8
...
看著是不是感覺很符合這個(gè)公式：
這個(gè)公式其實(shí)很好理解，因?yàn)樽詈笠淮我瓷?1 個(gè)臺階，要么是上 2 個(gè)臺階，上一個(gè)臺階前面的種數(shù)有 f(x - 1) 種，上 2 個(gè)臺階前面有 f(x - 2) 中方式，所以 f(x) 就是這兩個(gè)加起來咯。
對著這個(gè)公式寫代碼其實(shí)很簡單：
public?int?climbStairs(int?n)?{
????int?p?=?0,?q?=?0,?r?=?1;
????for?(int?i?=?1;?i?<=?n;?++i)?{
????????p?=?q;
????????q?=?r;
????????r?=?p?+?q;
????}
????return?r;
}
解題方案二：斐波那契數(shù)列
我們把這個(gè)題結(jié)果的數(shù)列列出來看一下：
1,?2,?3,?5,?8,?13,?21?...
如果上大學(xué)的時(shí)候沒有偷懶的話，這個(gè)數(shù)列應(yīng)該很有名，它是斐波那契數(shù)列，又叫黃金分割數(shù)列。
有關(guān)斐波那契是由一個(gè)通項(xiàng)公式的：
有了這個(gè)通項(xiàng)公式，寫代碼應(yīng)該沒啥問題了，照著寫就好了。
至于這個(gè)通項(xiàng)公式的推導(dǎo)，我就不介紹了，感興趣的同學(xué)可以自己百度去查，主要是這個(gè)公式打起來真的很費(fèi)勁。
public?int?climbStairs_1(int?n)?{
????double?sqrt5?=?Math.sqrt(5);
????//?題目下標(biāo)從?0?開始,因此求?n?+?1
????double?fibn?=?Math.pow((1?+?sqrt5)?/?2,?n?+?1)?-?Math.pow((1?-?sqrt5)?/?2,?n?+?1);
????return?(int)(fibn?/?sqrt5);
}
其實(shí)答案中還有一個(gè)方案是叫 「矩陣快速冪」 ，這個(gè)思想我了解清楚了，但是答案中給的題解沒咋看懂。
原諒我把大學(xué)的線性代數(shù)都不知道扔哪里去了，今天晚上基本上研究了半個(gè)晚上矩陣也沒大懂，哎，果然上是年紀(jì)了，以前學(xué)的東西都忘得差不多了。
