剑指 Offer 10- I. 斐波那契数列

题目描述：

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

示例：

输入：n = 2
输出：1

输入：n = 5
输出：5

思路：

f(n)=f(n-1)+f(n-2)

1
2
3
4
5
6
7
//f(n)=f(n-1)+f(n-2)
var fib = function(n) {
    if(n === 0 || n === 1) {
         return n
     }
    return fib(n-1) + fib(n-2)
 };

代码：

结果要记得取模！！ 

1
2
3
4
5
6
7
8
9
10
11
var fib = function(n) {
    let result = []
    for(let i=0; i<= n; i++) {
        if(i=== 0 || i=== 1) {
            result[i] = i
        } else {
            result[i] = (result[i-1] + result[i-2])% 1000000007
        }
    }
    return result[n]
};