- 作者： 负雪明烛
- id： fuxuemingzhu
- 个人博客：http://fuxuemingzhu.cn/
- 个人微信公众号：负雪明烛
题目地址：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
题目描述
写一个函数，输入 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
解题方法
递归
求第 n 个数的时候需要知道第 n-1 个数和第 n-2 个数，也就是大问题被拆解成了小问题，这很符合递归的逻辑。
斐波那契数列是我们学过的第一个递归问题，很快我们就写出来下面的 python 代码：
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return (self.fib(n - 1) + self.fib(n - 2)) % 1000000007
- 时间复杂度：
O
(
2
n
)
O(2 ^ n)
O(2n)，类似于二叉树的节点数。
- 空间复杂度：
O
(
n
)
O(n)
O(n)，栈的深度。
但是我们提交了之后，发现超时了。为什么呢？
因为，直接递归解法由于有很多的重复计算，比如计算 fib(3) 的时候需要计算 fib(2) 和 fib(1)；而计算 fib(4) 的时候，又计算了一遍 fib(3)。
为了解决重复计算的问题，可以使用「记忆化搜索」，即可以使用字典保存计算过了的数字，省去了重复的计算，速度很快。
Python 代码如下：
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.keep = {0:0, 1:1}
def Fibonacci(self, n):
if n in self.keep:
return self.keep[n]
else:
fn = self.Fibonacci(n - 1) + self.Fibonacci(n - 2)
self.keep[n] = fn
return fn
在 python3 中，可以使用语言自带的「记忆化递归」的注解：@functools.lru_cache()，它的用法只有一行，即在要执行记忆化的函数上面加上一行注解，即可在语言级别的自动化的记忆化递归。
class Solution:
@functools.lru_cache()
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return (self.fib(n - 1) + self.fib(n - 2)) % 1000000007
- 时间复杂度：
O
(
n
)
O(n)
O(n)，避免了重复的计算。
- 空间复杂度：
O
(
n
)
O(n)
O(n)，栈的深度。
动态规划
在「记忆化搜索」的基础上，再迈出一步，就能得到「动态规划」的解法。它们都是把大问题拆解成小问题的方法。
- 「记忆化搜索」：是
从顶向下的思路，即把大问题一步步拆分成小问题； - 「动态规划」：是
从底向上的思路，即先得到小问题，然后再一步步推到出大问题。
动态规划的推导过程如下。
- 定义状态：
dp[i]表示斐波拉契数列的第 n 个数字； - 状态转移方程：
F(N) = F(N - 1) + F(N - 2), 其中 N > 1. - 初始条件：
F(0) = 0, F(1) = 1
Python 的代码如下：
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
return dp[n]
C++ 代码如下：
class Solution {
public:
int fib(int n) {
vector<int> dp(101, -1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
}
};
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
n
)
O(n)
O(n)
由于 dp[i] 的状态只跟 dp[i - 1] 和 dp[i - 2] 有关，所以可以进行状态的压缩，从而降低空间复杂度。即使用 3 个变量，分别表示
python 代码如下：
class Solution:
def fib(self, n: int) -> int:
a, b = 0, 1
for i in range(n):
a, b = b, (a + b) % 1000000007
return a
日期
2018 年 3 月 9 日
2021 年 8 月 5 日 —— 昨天去拍婚纱照了