一、题目描述
题目来自剑指Offer 10-I.难度简单。
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：1
示例 2：
输入：n = 5 输出：5
提示：
0 <= n <= 100
二、题目解析
斐波那契数列的定义是f(n)=f(n-1)+f(n-2)，生成第n向的做法有以下三种：
1. 递归法
原理：把f(n)的问题拆分成f(n-1）和f(n-2)两个子问题计算，并递归，终止条件是f(0)和f(1)。缺点：需要进行重复大量的计算，例如f(n) 和 f(n - 1)f(n−1) 两者向下递归需要 各自计算 f(n - 2)f(n−2) 的值。
2. 记忆化递归法
原理：在递归的基础上，新建一个长度为n的数组，用于在递归时存储f(0)到f(n)的数值，每次递归前，先查看数组内有没有需要的数字，这样可以避免重复的递归计算。缺点：需要使用O（N）的额外空间
3. 动态规划
原理：以斐波那契数列性质为转移方程f(n)=f(n-1)+f(n-2)状态定义：设dp为一维数组，其中dp[i]的值代表斐波那契数列的第i个数字转移方程：dp[i]=dp[i-1]+dp[i-2]，对应数列f(n)=f(n-1)+f(n-2)初始状态：dp[0]=0，dp[1]=1，即初始化前两个数字返回值：dp[n]，即斐波那契数列的第n个数字。
三、参考代码
#递归法
#超出时间限制
class Solution:
def fib(self, n: int) -> int:
# 递归的终止条件
if n == 0:
return 0
if n == 1:
return 1
# 递归式
return self.fib(n-1)%1000000007 + self.fib(n-2)%1000000007
# 记忆化递归法
# 力扣提交会超出时间限制，虽然没有重复递归，但是递归和回溯的时间复杂度也很大
class Solution:
def fib(self, n: int) -> int:
# 存储数值
memo = {}
# 查表
if n in memo:
return memo[n]
else:
if n == 0 or n ==1:
f = n
else:
f = (self.fib(n-1) + self.fib(n-2)) % 1000000007
memo[n] = f
return f
# 动态规划
class Solution:
def fib(self, n: int) -> int:
dp = {}
dp[0] = 0
dp[1] = 1
for i in range(2,n+1):
dp[i] = (dp[i-1]+dp[i-2]) % 1000000007
return dp[n]
四、其他笔记
为什么要对结果进行取模运算？
大数越界：随着n增大，f(n)会超过Int32甚至Int64的取值范围，导致最终的返回值错误。
空间复杂度优化
若新建长度为n的dp列表，则空间复杂度为O（N）
由于dp列表第 i 项只与第 i - 1 项和第 i - 2 项有关，因此只需要初始化三个变量sum,a,b，利用辅助变量sum使a,b两数字交替前进即可。节省了dp列表的空间，因此空间复杂度降至O（1）。
# 不需要定义dp列表
class Solution:
def fib(self, n: int) -> int:
if (n == 0 or n ==1):
return n
a , b = 0 , 1
for i in range(2,n+1):
sum = (a + b) % 1000000007
a = b
b = sum
return sum
