剑指Offer编程题-斐波那契数列 | 我的个人生活记录

题目：斐波那契数列

题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39

解题思路

斐波那契数列：F(0) = 0, F(1) = 1, F(2) = 1, F(3) = F(2) + F(1), … , F(n) = F(n-1) + F(n-2)

• 看到这个第一反应是用递归，然而由于递归的重复计算太多，时间复杂度太高，不能通过测试
• 用循环实现
• 讨论区大神的动态规划版，原理和循环类似，但是更节省空间。
• 补充：斐波那契数列的通用公式

实现

python

递归（不能通过测试）：

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n <= 1:
            return n
        return self.Fibonacci(n-1) + self.Fibonacci(n-2)

循环：

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        li = []
        li.append(0)
        li.append(1)
        for x in range(2,n+1):
            li.append(li[x-1] + li[x-2])
        return li[n]

动态规划：

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        a = 0
        b = 1
        while n:
            b += a
            a = b - a
            n -= 1
        return a

直接用通用公式计算：

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        return int(1/(5**0.5)*(((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n))