一、问题
写一个函数，输入 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
二、解法
解法一
思路：递归
递归算法写起来是最简单的，我们只要定义好递归出口，不停的循环调用就好了。但是递归算法存在一个问题，重复计算的问题。在这个问题中，我们以f(5)为例。如下图，f(3)、f(2)分别调用了2次和3次。我们知道二叉树的节点数和层数有关系，求斐波拉契数列的第n个数，递归调用树有n-1层，那么基本上需要计算指数级别的次数。时间复杂度和空间复杂度都是O(2^n)，很恐怖。
img
- 定义好递归调用出口。n=0,f(n) = 0;n=1,f(n) = 1;
- f(n) = f(n-1)+f(n-2)
具体实现：java
class Solution {
public int fib(int n) {
if(n == 0){
return 0;
}
if(n == 1) {
return 1;
}
return fib(n-1) + fib(n - 2);
}
}
解法二
思路：预处理
初始化n1为0和n2为1
n1和n2用来表示f(n-2)和f(n-1)
循环遍历到n，n2就是f(n)
时间复杂度：O(n),空间复杂度O(1)
具体实现：java
class Solution {
public int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int n1 = 0;
int n2 = 1;
for (int i = 2; i <= n; i++) {
int t = n1 + n2;
n1 = n2;
n2 = t;
n2 = n2>1000000007 ? n2 % 1000000007: n2;
}
return n2;
}
}
总结
斐波拉契数列的思想有助于我们解决很多问题，在很多情况下，只要我们找出f(n)和f(n)-1的关系，就可以解决问题。下一章，我们将讨论斐波拉契在一些场景的应用。
