剑指offer—07斐波那契数列(Python)
【题目】大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）n<=39。
【思路】斐波那契数列：第n项是第n-1项和第n-2项的和；
当 n=0,f(n)=0;
n=1,f(n)=1;
n>1,f(n)=f(n-1)+f(n-2)
看到这个通项，就想使用递归来做…
【递归实现】
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
if n == 0:
return 0
if n == 1:
return 1
if n > 1:
num = self.Fibonacci(n-1) + self.Fibonacci(n-2)
return num
return None
# write code here
结果运行超时，该方法里面有很多的重复计算，时间复杂度为O(n^2),只能换种思路，因为第n项的值是前两项的和，那我们每次计算都保存前两项的值用于下一次的计算，进行一个循环，最终即可得到第n项的值。
【动态规划】
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
if n == 0:
return 0
if n == 1:
return 1
if n > 1:
Pre = 1
Prepre = 0
num = 0
for i in range(0,n-1):
num = Pre +Prepre
Prepre = Pre
Pre = num
return num
return None
# write code here
每次仅保留最近两次的结果，计算一次更新一次，时间复杂度为O(n)
作者：草木向阳
