写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

一.暴力递归

直接上代码：

class Solution(object):
    def fib(self, n):
        if n==0:
            return 0
        elif n==1:
            return 1
        else:
            return self.fib(n-1)+self.fib(n-2)
tt=Solution()
s=tt.fib(6)
print(s)#8

二.列表存值

对于小一点的数字求解没有问题，但是如果数字比较大（斐波那契第45位已经是10位数了），就很耗时甚至IDE求不出来，这个时候我们就不能再使用递归了。

class Solution(object):
    def fib(self, n):
        if n==0:
            return 0
        elif n==1:
            return 1
        else:
            zu=[]
            zu.append(0)
            zu.append(1)
            for i in range(2,n+1):
                zu.append((zu[i-1]+zu[i-2]))
            return zu[-1]

tt=Solution()
s1=tt.fib(6)
print(s1)#8
s2=tt.fib(66)
print(s2)#27777890035288

三.生成器

def fib(n):
    i = 0
    a, b = 0, 1
    while i < n:
        a, b = b, a + b
        i += 1
        yield b


for x in fib(5):
    print(x)

生成器参考链接

四.动态规划

def fibonacci(n):
    if n < 2:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 1)


def dyna_fibonacci(n):
    if n < 2:
        return n
    else:
        a, b = 0, 1
        for _ in range(n - 1):
            a, b = b, a + b
        return b


if __name__ == '__main__':
    t1 = time.time()
    fibonacci(100)
    t2 = time.time()
    dyna_fibonacci(100)
    t3 = time.time()
    print("Time required for using recursion:", t2 - t1)
    print("Dynamic Planning Duration:", t3 - t2)

动态规划参考