斐波那契数列 | 葵花宝典

# 介绍

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

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

1
2

给定 N，计算 F(N)。

示例:

//示例1:
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

//示例2:
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

//示例3:
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 题解一

最简单的接发就是按照题目描述直接套用，上代码

/**
 * @param {number} N
 * @return {number}
 */
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

这是一种递归的方式，当然里面会有一些重复的计算，占用内存啥的，目的是能达成，就是性能差一点。

# 题解二

相比递归的话，这里实现一个递推+缓存记忆的实现方式，代码如下

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    let cace=[]
    for(let i=0;i<=N;i++){
        if(i==0 || i==1){
            cace[i]=i
        }else{
            cace[i]=cace[i-1]+cace[i-2]
        }
    }
    return cace[N]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这是一种递推的方式，利用数组来缓存相加的值，直接return对应的N就可以了，当然，递推里面还可以用变量的方式来缓存，数组只是一直手段。

# 题解三

其实这也算是一种递推+缓存的方式，只是里面的具体实现不是数组，而是用的变量。代码如下

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    var n1 = 0, n2 = 1, sum;
    if(N==0) return 0
    if(N<=2) return n1+n2
    for (let i = 2; i <= N; i++) {
        sum = n1 + n2
        n1 = n2
        n2 = sum
    }
    return sum
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 总结

其实斐波那契数列的解法有很多，还可以去套用数学里面的一些公式来减少重复计算。在解题时，最开始想到的都是递归，但是就性能而言，确实有点差，所以优化一下采用空间换时间的做法，把累加值保存下来，以免出现重复计算。当然方法千千万，我只列出了简单的三种。