一、斐波那契数列
斐波那契数列是这样的一组数列：1、1、2、3、5、8、13、21、34、……
在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
即大于2的部分是由前两个相加获得。
若要求第 N 个数的值，我们可以用递归也可以通过迭代的方式求解
1、递归
def fibonacci(n):
if n == 1 or n == 2:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
2、迭代
def fibonacci(n):
dic = dict()
dic[1] = 1
dic[2] = 2
for i in range(2, n+1):
dic[i] = dic[i-1] + dic[i-2]
return dic[n]
二、衍生题
1、跳台阶 / 爬楼梯
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
想象一下，我们从最顶层的台阶开始算起，在最顶层，能够用一次走完的，可能最后只剩一个台阶，也可能只剩两个台阶。
然后除去最顶层这一个或者两个台阶，剩下的也是这样，一直循环下去，是不是最后就到了底层？
也就是方式不断地往上加，类似斐波那契数列。
说得可能有点不够通俗，我们通过数学归纳法验证一下：
一个台阶，跳一次；
两个台阶，可以跳一次，也可以分两阶跳，总共两种；
三个台阶，有三种方式；
四个台阶，有五种…
这样看是不是就是斐波那契数列。
那么通过编程的方式，参照上面的代码。
2、跳台阶II
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
这道题跟上一道题地不同就在于没有了一次跳多少阶的条件。
F(1) = 1
F(2) = F(2-1) + F(2-2)
F(3) = F(3-1) + F(3-2) + F(3-3)
...
其中 F(n-m) 表示 n 阶一次跳 m 阶的次数。
F(n) = F(n-1) + F(n-2) + F(n-3) + ... + F(n-(n-1)) + F(n-n) ①
F(n-1) = F(n-2) + F(n-3) + ... + F(n-(n-1)) + F(n-n) ②
① - ② 得：F(n) = 2 x F(n-1)
因此代码如下：
def jumpFloorII(number):
# write code here
if number == 0 or number == 1:
return 1
return jumpFloorII(number - 1) * 2
关注 大数据的奇妙冒险 ，解锁更多知识！转载请注明出处
