题目描述

大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。n<=39。

解法 1: 数学定义

根据数学定义：f(n) = f(n - 1) + f(n - 2)。最初始情况是f(0) = 0和f(1) = 1。

因此直接循环更新即可。时间复杂度 O(N)，空间复杂度 O(1)。

// 原文地址：https://xxoo521.com/2019-12-25-fei-bo-na-qi/
// ac地址：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3

/**
 * @param {number} n
 * @return {number}
 */
function Fibonacci(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let a = 0,
        b = 1;
    for (let i = 2; i < n; ++i) {
        let c = a + b;
        a = b;
        b = c;
    }

    return a + b;
}

解法 2: 递归 + 动态规划

根据数学定义：f(n) = f(n - 1) + f(n - 2)，代码可以实现为递归形式。

但是以 f(5)为例，它的过程如下：

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
...省略

注意在第 2 步和第 3 步中，我们计算了 2 次 f(3)的值。当要求的 n 越大的时候，重复计算就会越多，时间复杂度就会越高。

在动态规划的一种做法中，可以借助“备忘录”来实现结果的缓存，避免重复计算。

代码如下，时间复杂度是 O(N)，空间复杂度是 O(1)。

// 原文地址：https://xxoo521.com/2019-12-25-fei-bo-na-qi/
// ac地址：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3

/**
 * @param {number} n
 * @return {number}
 */
function Fibonacci(n) {
    const cache = {
        0: 0,
        1: 1
    };
    return __Fibonacci(n);

    /**
     * @param {number} n
     * @return {number}
     */
    function __Fibonacci(n) {
        if (cache[n] !== undefined) {
            return cache[n];
        }

        cache[n] = __Fibonacci(n - 1) + __Fibonacci(n - 2);
        return cache[n];
    }
}

专注前端与算法的系列干货分享，欢迎关注(¬‿¬)

image