斐波那契數(shù)列（Fibonacci sequence），又稱(chēng)黃金分割數(shù)列。

解法：

1、遞歸

2、累加（去重復(fù)）

3、矩陣，矩陣乘法求遞推。

此圖左側(cè)應(yīng)該是（f（n）,f（n-1））

http://www.cnblogs.com/kongse-qi/p/6901951.html

http://blog.csdn.net/qq_34342154/article/details/77104452

http://www.cnblogs.com/xudong-bupt/archive/2013/03/19/2966954.html

http://www.matrix67.com/blog/archives/276

問(wèn)題轉(zhuǎn)換：

題目一：寫(xiě)出一個(gè)函數(shù)，輸入n，求斐波那契數(shù)列的第n項(xiàng)。

題目二：一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。請(qǐng)求青蛙上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。

題目三：?用2*1的小矩形橫著或豎著去覆蓋更大的矩形，用8個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*8的大矩形，總共有多少種方法？

矩形覆蓋-我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？

青蛙問(wèn)題

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

其實(shí)就是斐波那契數(shù)列問(wèn)題。

假設(shè)f(n)是n個(gè)臺(tái)階跳的次數(shù)。

f(1) = 1

f(2) 會(huì)有兩個(gè)跳得方式，一次1階或者2階，這回歸到了問(wèn)題f(1),f(2) = f(2-1) + f(2-2)

f(3) 會(huì)有三種跳得方式，1階、2階、3階，那么就是第一次跳出1階后面剩下：f(3-1);第一次跳出2階，剩下f(3-2)；第一次3階，那么剩下f(3-3).因此結(jié)論是

f(3) = f(3-1)+f(3-2)+f(3-3)

f(n)時(shí)，會(huì)有n中跳的方式，1階、2階...n階，得出結(jié)論：

f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1) == f(n) = 2*f(n-1)

所以，可以得出結(jié)論

http://www.matrix67.com/blog/archives/276

https://segmentfault.com/q/1010000003797424?sort=created

http://www.cnblogs.com/SymenYang/p/3661466.html