题目描述
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 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
题目解答
解法一：递归方式（时间复杂度太高）
var fib = function(n
) {
if(n
<=0){
return 0;
}
if(n
==1){
return 1;
}
return fib(n
-1)+fib(n
-2);
};
该方式需要大量的重复计算，效率低下。可以考虑将已经计算好的中间值保存下来，需要的时候直接查找。
更简单的方法是，从下往上计算，先算f(0)和f(1)，依次计算。该方法的时间复杂度为O(n)。
解法二：循环实现（O(n)）
var fib = function(n
) {
if(n
<=0){
return 0;
}
if(n
==1){
return 1;
}
var fibN
= 0;
var fibOne
= 0;
var fibTwo
= 1;
for(var i
=2;i
<=n
;i
++){
fibN
= (fibOne
+ fibTwo
)%(1e9+7);
fibOne
= fibTwo
;
fibTwo
= fibN
;
}
return fibN
;
};
