剑指Offer题解 - Day16

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

力扣题目链接[1]

写一个函数，输入 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

「提示：」

• 0 <= n <= 100

思路：

本题不能使用暴力法进行破解。因为斐波那契数列直接计算的话，会产生很多重复的计算。导致运算时间指数级的增加，因此这里一定要避免使用暴力法。

换个角度思考，其实计算当前值的时候，只需要关心前面两个值。因此这里动态缓存前两个值，便可以得到最终的结果，这样做可以避免无效的计算。

动态规划

这里采取动态规划的方法进行求解。首先需要找到动态规划方程和初始值。显然，这里遵循以下方程：

• f(n + 1) = f(n) + f(n - 1)
• f(0) = 0, f(1) = 1
• 最终结果返回f(n)

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let sum = 0; // 初始化和
    let a = 0; // 初始化第一项
    let b = 1; // 初始化第二项
    for (let i = 0; i < n; i++) {
        sum = (a + b) % 1000000007; // 大数进行取模
        a = b; // 两数交替前进
        b = sum;
    }
    return a; // a就是f(n)
};

• 「时间复杂度 O(n)」。
• 「空间复杂度 O(1)」。

分析：

首先找到动态规划方程，然后定义初始值。斐波那契的核心就是第三数为前两数之和。因此我们只需要额外维护三个变量，用来动态缓存计算的结果。

按照题目的要求，这里要对大数进行取模运算。然后对声明的a、b变量交替赋值，达到前进的效果。

最后循环结束后，返回a的值，也就是f(n) 的值。

复杂度方面，由于需要循环n次，因此时间复杂度是O(n) ；而维护了常量级别的变量，因此空间复杂度是O(1)。

总结

本题考查动态规划方程的编写，除了使用动态规划，本题还可以通过维护额外的哈希表用来存储计算的值，但是这样会产生空间复杂度为O(n) 的消耗，不是最优解。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50fxu1/