第N个泰波那契数（1137）

题目

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例

输入：n = 4 输出：4

解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

输入：n = 25 输出：1389537

提示

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

算法

迭代

export const tribonacci = (n) => {
	const tri = [];
	(tri[0] = 0), (tri[1] = 1), (tri[2] = 1);
	for (let i = 3; i <= n; i++) {
		tri[i] = tri[i - 1] + tri[i - 2] + tri[i - 3];
	}
	return tri[n];
};

递归

普通递归（超时）

export const tribonacci = (n) => {
	if (n === 0) return 0;
	if (n === 1 || n === 2) return 1;
	return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
};

记忆化的递归

普通递归会超时，我们使用一个数组cache来缓存已计算的结果

export const tribonacci = (n) => {
	const cache = [];
	const recursion = (n) => {
		if (cache[n]) return cache[n];
		if (n === 0) return 0;
		if (n === 1) return 1;
		if (n === 2) return 1;
		cache[n] = recursion(n - 1) + recursion(n - 2) + recursion(n - 3);
		return cache[n];
	};
	return recursion(n);
};

尾递归

因为尾递归调用的是当前活动空间内的最后一条待执行语句，所以调用栈在调用新函数时不必保存当前栈帧，而直接覆盖当前栈帧，这样就不会爆栈

export const tribonacci = (n, r1 = 0, r2 = 1, r3 = 1) => {
	if (n <= 0) return r1;
	return tribonacci(n - 1, r2, r3, r1 + r2 + r3);
};

通项公式 + 递归

有已知可得：

T(n+1) = T(n) + T(n-1) + T(n-2)
T(n) = T(n-1) + T(n-2) + T(n-3)

两式相减：

T(n+1) - T(n) = T(n) - T(n-3)

化简：

T(n+1) = 2 * T(n) - T(n-3)

将n = n+1带入得通项公式：

T(n) = 2 * T(n-1) - T(n-4)

export const tribonacci = (n) => {
	if (n === 0) return 0;
	if (n === 1 || n === 2) return 1;
	if (n === 3) return 2;
	return 2 * tribonacci(n - 1) - tribonacci(n - 4);
};