【经典算法题目】斐波那契数列

斐波那契数列

斐波那契数列定义为：当n=0或1时，f(n)=n；当n>1时，f(n)=f(n-1)+f(n-2)。
求斐波那契数列的第n项。

递归算法求解

def Fibonacci(n):
    if n<0:
        return 0
    elif n<=1:
        return n
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

递归算法求解斐波那契数列第n项存在大量的重复运算，算法的时间复杂度随着n的增大呈现指数增长，时间的复杂度为O(2^n)，即2的n次方

迭代算法求解

def Fibonacci(n):
    if n<0:
        return 0
    elif n<=1:
        return 1
    else:
        f_n1=1
        f_n2=0
        i=2
        while i<=n:
            f_n=f_n1+f_n2
            f_n1=f_n
            f_n2=f_n1
        return f_n

这种迭代算法求解不存在重复运算，算法的时间复杂度随着n的增大呈现线性增长，时间的复杂度为O(n)，空间复杂度为O(1).

斐波那契数列变种

变种1：青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求该青蛙跳上一个n级台阶总共有多少种跳法。

变种2：矩阵覆盖

用8个2*1的小矩阵无重叠地覆盖一个2*8的大矩阵，总共有多少种方法？

• 参考《剑指Offer》