// 斐波那契数 （通常用 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
js
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
if(n == 0) return 0
if(n == 1) return 1
return fib(n-1) + fib(n-2)
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
简单递归
js
var fib = function (n) {
let a = new Array(n + 1)
if (n == 0) return 0
if (n == 1) return 1
a[0] = 0
a[1] = 1
for (let i = 2; i <= n; i++)
a[i] = a[i - 1] + a[i - 2]
return a[n]
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
简单数组动态规划
js
var 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;
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
动态规划 初始化：设定初始值 p = 0, q = 0, r = 1。这相当于 F (0) = 0, F (1) = 1。 循环计算： 从 i = 2 开始，直到 i = n。 在每次循环中： 将 p 更新为 q 的值。这意味着 p 保持前一轮 q 的值。 将 q 更新为 r 的值。这意味着 q 保持前一轮 r 的值。 计算新的 r 值，它是 p 和 q 的和。这相当于 F (i) = F (i-1) + F (i-2)。 返回结果：循环结束后，r 就是第 n 个斐波那契数。 通过这种方式，我们只用了常量空间（p, q, r 三个变量）就完成了对斐波那契数的计算，实现了空间复杂度为 O (1) 的算法。
js
var fib = function (n) {
const sqrt5 = Math.sqrt(5);
const fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
return Math.round(fibN / sqrt5);
};1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
数学方法
这个公式利用了黄金分割比和其共轭来计算斐波那契数列的第 n 项。