斐波那契数

2022 年 10 月 08 日
广东
本文字数：898 字
阅读完需：约 3 分钟

LeetCode 75 学习计划适用于想为技术面试做准备但不确定应该聚焦于哪些题目的用户。学习计划中的题目都是经过精心挑选的，Level 1 和 Level 2 学习计划是为初级用户和中级用户准备的，题目覆盖了大多数中层公司面试时所必需的数据结构和算法，Level 3 学习计划则是为准备面试顶级公司的用户准备的。来源

第 10 天

斐波那契数

难度：简单

题目

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

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：
输入：n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4输出：3解释：F(4) = F(3) + F(2) = 2 + 1 = 3

复制代码

题解

方法 1：是最简单的解法但也是最耗时的解法。

// 解法1var fib = function(N) {    if (N < 2) return N;    return fib(N - 1) + fib(N - 2);}

复制代码

方法 2：从 i=2 开始迭代 N，将第 i 个元素设置前两个元素的和，这样最后一个元素的值就是斐波那契数。

// 解法2var fib = function(N) {    if ( N <= 1) return N;    const result = new Array(N);    result[0] = 0;    result[1] = 1;    for (let i = 2; i < N + 1; i++) {        result[i] = result[i - 1] + result[i - 2];    }    return result[N];};

复制代码

方法 3：由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1)。

根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n)的实现。由于 F(n) 只和 F(n-1) 与 F(n-2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)。

// 解法3var fib = function(n) {    if (n < 2) {        return n;    }    let p = 0, q = 0, r = 1;    for (let i = 2; i <= n; i++) {        p = q;        q = r;        r = p + q;    }    return r;};

复制代码

总结

滚动数组的解法太棒了，除了最常规的递归思想，滚动数组以更低的空间复杂度解题更优~

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/c5ab179dabda41b5193a2d976】。文章转载请联系作者。

掘金安东尼

关注

安东尼陪你度过漫长编程岁月~ 2022.07.14 加入

真正的大师，永远怀着一颗学徒的心（易）

发布

暂无评论

创作场景

斐波那契数

第 10 天

斐波那契数

题目

题解

总结

掘金安东尼

评论