斐波那契数（509）

题目

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

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

给定 N，计算 F(N)。

示例

输入：2 输出：1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

输入：3 输出：2

解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

输入：4 输出：3

解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

提示

0 ≤ N ≤ 30

算法

递归

export const fib = (n) => {
	if (n <= 1) return n;
	return fib(n - 1) + fib(n - 2);
};

比内公式（斐波那契数列通项公式）

比内公式: !(比内公式)[https://bkimg.cdn.bcebos.com/formula/6a79d456d05de649023252cae49590da.svg]

export const fib = (n) => {
	return (1 / Math.sqrt(5)) * (((1 + Math.sqrt(5)) / 2) ** n - ((1 - Math.sqrt(5)) / 2) ** n);
};

记忆化的自底向上的计算

声明数组用来保存之前计算的斐波那契数，循环求解目标数

export const fib = (n) => {
	if (n <= 1) return n;
	const cache = [0, 1];
	for (let i = 2; i <= n; i++) {
		cache[i] = cache[i - 1] + cache[i - 2];
	}
	return cache[cache.length - 1];
};

记忆化的自顶向下的递归

类似递归的方法，只是这里用cache来保存之前求出的斐波那契数，如果存在于cache中则直接返回不再继续递归求解

export const fib = (n) => {
	if (n <= 1) return n;
	const cache = [0, 1];
	const memorize = (n) => {
		if (cache[n] != null) return cache[n];
		cache[n] = memorize(n - 1) + memorize(n - 2);
		return memorize(n);
	};
	return memorize(n);
};

自底向上的迭代

使用cur保存当前值，使用prev1、prev2保存之前的两个值，迭代的求解目标数

export const fib = (n) => {
	if (n <= 1) return n;
	let cur = 1,
		pre1 = 1,
		pre2 = 0;
	for (let i = 2; i <= n; i++) {
		cur = pre1 + pre2;
		pre2 = pre1;
		pre1 = cur;
	}
	return cur;
};