斐波那契数列

• 题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
  n<=39
• 解答

# -*- coding:utf-8 -*-
class Solution:
    '''时间复杂度过大，太多重复计算，超时'''
    def Fibonacci(self, n):
        if n == 0 or n == 1:
            return n
        return self.Fibonacci(n - 1) + self.Fibonacci(n - 2)

    ''' 用两个变量交替赋值，值得借鉴'''
    def Fibonacci3(self, n):
        # write code here
        f0, f1 = 0, 1
        if n == 0:
            return 0
        elif n == 1:
            return 1
        for k in range(2, n + 1):
            f0, f1 = f1, f0 + f1
        return f1

    '''AC  数列为0，1，1，2'''
    def Fibonacci2(self, n):
        anslist = []
        anslist.append(0)
        anslist.append(1)
        if n == 0 or n == 1:
            return anslist[n]
        k = 2
        while k <= 39:
            anslistk = anslist[k - 1] + anslist[k - 2]
            anslist.append(anslistk)
            k += 1
        return anslist[n]

if __name__ == '__main__':
    n = 6
    s = Solution()
    for i in range(0, n):
        print(s.Fibonacci(i))