題目描述

假設你正在爬樓梯。需要?n?階你才能到達樓頂。

每次你可以爬?1?或?2?個臺階。你有多少種不同的方法可以爬到樓頂呢？

（詳情請見leetcode70）

動態(tài)規(guī)劃

一開始用遞歸寫，然后超時了...

隨后開了大小為n的數(shù)組，后來發(fā)現(xiàn)沒有必要，只需要三個整型...

大致思路：

在第 n 級臺階上的人，一定是從第 n-1 或第 n-2 級臺階邁上來的

由此可以列出狀態(tài)轉移方程

邊界條件是，

推薦的寫法是利用滾動數(shù)組思想

接下來是從答案抄來的代碼

復雜度分析

時間復雜度：循環(huán)執(zhí)行 n 次，每次花費常數(shù)的時間代價，故漸進時間復雜度為 O(n)。

空間復雜度：這里只用了常數(shù)個變量作為輔助空間，故漸進空間復雜度為 O(1)。

矩陣快速冪

是的，這種題對于大神來講，是用來秀肌肉的orzorzorz

官方給出的答案里說，隨著n的增大，時間復雜度會以O(n)增長

所以我們試圖把時間復雜度降至O(logn)

利用小學二年級知識——矩陣乘法，推導出下面神奇的遞推式

然后：

定義矩陣

問題變成了求解矩陣M的n次方問題

普通求法時間復雜度為O(n)，為了降低時間復雜度

使用魔法快速冪加速n次方的求解

（快速冪視頻友情鏈接）

直接上代碼...

納尼(⊙o⊙)？這是什么......

好的......中間那個函數(shù)是取矩陣M的快速冪用的

相當于把n二進制形式有1的位數(shù)取出，通過M不斷做2次方次方（？）

求解出最終的M的n次方

具體可以看上面那個視頻

那么，神魔情況下會用快速冪呢？

需要用到高等數(shù)學微分方程和線性代數(shù)的知識！orz

復雜度分析

時間復雜度：同快速冪，O(logn)。

空間復雜度：O(1)。

通項公式

不知道大佬們有沒有看出來，這個遞推式恰好是斐波那契數(shù)列

所以我們可以站在巨人的肩膀上

直接用公式求第n項！

（推導過程需要用到線性代數(shù)知識！可以前往leetcode70答案區(qū)看視頻，一時半會我也說不清楚orz）

公式：

代碼

打表法

找個層數(shù)在50左右的樓，走一走，數(shù)一數(shù)，既鍛煉了身體，也增強了腦力！

寫在最后

只有不停奔跑，才能勉強停在原地！