題目描述：斐波那契數(shù)列

題目實現(xiàn)：

用遞歸的方法解決：

傳個10進(jìn)去，我們可以畫出這樣的調(diào)用圖

可以看到f(7)被調(diào)用了3次，f(6)被調(diào)用了3次等重復(fù)計算情況。重復(fù)節(jié)點(diǎn)的數(shù)量會隨著n的增大而急劇增加

更簡單的方法是從下往上計算

把結(jié)果擺出來可以發(fā)現(xiàn)大于2之后每一項都是前2項之和

書中代碼是這樣的

這個代碼還可以簡化成下面這樣：

相關(guān)題目1：一個青蛙可以跳上一級臺階，也可以跳上2級臺階。求該青蛙跳上一個n級臺階總共有多少種跳法。

解題思路：畫圖比較好理解，如下圖

聰明的小伙伴應(yīng)該看出來就是：1,1,2,3,5 斐波那契數(shù)列了。

我們可以換個角度看：那就是青蛙已經(jīng)在第三層了，那他要不是從第2層跳上來的，要不就是從第一層跳上來的。

那他有幾種方法跳到第二層呢 有2種 有幾種方法跳到第一層 有1種 。 所以第三層跳法是1+2=3種。

或者我們看他在第二層的時候，要不是從0層跳上來的，要不就是從1層跳上來的。這時候第一層的跳法是可以復(fù)用的，

在第三層的時候，可以復(fù)用第一層的跳法結(jié)果和第二層的跳法結(jié)果。

所以設(shè)n為層數(shù)，第n層的跳法數(shù)目等于第n-1層的跳法數(shù)目加上n-2層的跳法數(shù)目。

也就是：f(n)=f(n-1)+f(n-2)。算法實現(xiàn)和上題一樣。

本題擴(kuò)展：條件改成：一次可以跳n級，此時跳上一個n級臺階總共有多少種跳法，書中給了公式f(n)=2^n-1 。也就是后一個是前一個的2倍。

算法實現(xiàn)：