題目：給定一個樓梯的臺階數(shù)，你可以一次跳一個臺階也可以跳兩個臺階，那么在給定的n個臺階時會有多少種跳法可以到達臺階的頂部。

其中1<=n<=45;

大家先好好想一想，找一找它的規(guī)律，然后完成下面的代碼：

int climbStairs(int n){

}

思路：這道題或許很多的同學(xué)會想到使用遞歸來實現(xiàn)，但會發(fā)現(xiàn)一個問題就是超時了，哈哈哈確實會超時，為什么會超時我一會再說，先講解題思路。

來分析不同的臺階數(shù)n有多少種跳法。

n=1,第一種跳法：先一步一步的來，先走一步看是否可以到達，發(fā)現(xiàn)可以即可完成。

n=2,第一種跳法：一步一步的來，先走一步看是否可以到達，發(fā)現(xiàn)不行，剩下的1個臺階還沒走，剩下的臺階又有集中跳法，發(fā)現(xiàn)只有一種，直接走一步即可完成；第二種跳法：這次先走兩步，看剩下多少個臺階，剩下的臺階數(shù)又可以有多少鐘跳法，發(fā)現(xiàn)沒有臺階了，那就是完成了。

n=3,第一種跳法：先走一步，看剩下還有多少個臺階沒走，n-1=2,還剩下兩個臺階沒走，剩下的兩個臺階又有多少種跳法呢，前面已經(jīng)分析了是2種，所以臺階為3的先走一步有兩種走法，也就是1->1->1,->2；第二種跳法：先走兩步看剩下還有多少個臺階，n-2=1,還剩下一個臺階，剩下的一個臺階有多少種跳法，在前面也分析了是1種，也就是說臺階數(shù)為3的只有1種跳法，即2->1.

下面的分析亦是如此，大家可以自己去分析，分析種大家有沒有發(fā)現(xiàn)說明問題或者現(xiàn)象?；蛟S很多朋友會發(fā)現(xiàn)這跟斐波那契數(shù)列很像，是的，其實就是它。還發(fā)現(xiàn)多加一個臺階數(shù)只需要將它的前兩個和前一個臺階數(shù)的跳法相加即可，這個大家應(yīng)該可以理解吧，也就是臺階數(shù)為n，n-1就是先走一步的情況，n-1個臺階數(shù)又有多少種跳法；n-2是先走2步的情況，n-2個臺階數(shù)又有多少種跳法。

法案1：遞歸法（但會超時）

很簡單吧，相信大家都能看的懂，遞歸首先就是找到它的規(guī)律，之后確定它的遞歸循環(huán)停止的條件，最后就是遞歸函數(shù)怎么去實現(xiàn)。

現(xiàn)在就來說一說使用遞歸為什么會超時吧。

?

時間復(fù)雜度就是遞歸需要循環(huán)多少次，2^0+2^1+2^2+.....+2^(n-1)=2^n-1;當(dāng)n=10是，2^10=1024,為了方便講解，2^10~=1000(千級),2^20~=1000*1000=1000000(百萬級),2^30~=1000000000(十億級),

2^40~=1000000000000(萬億級)。電腦一般一秒鐘可以處理十億個數(shù)據(jù)

這是計算n=40的斐波那契數(shù)列所需要的時間。如果再繼續(xù)往上計算，時間是相當(dāng)大的，甚至無法計算出來直到地球毀滅都計算不出來。

所以大家明白它為什么會超時了吧。

方案2：用空間換時間

?

其實也不是很復(fù)雜是吧。

?

總結(jié)

以上是生活随笔為你收集整理的leetcode--爬楼梯的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。