LeetCode笔记：第 N 个泰波那契数
问题
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入： n = 4
输出： 4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入： n = 25
输出： 1389537
提示：
0 <= n <= 37- 答案保证是一个 32 位整数，即
answer <= 2^31 - 1。
解法一
思路：
动态规划的思想
核心代码就是翻译公式 Tn+3 = Tn + Tn+1 + Tn+2，然后处理下三个边界值 n 为 0、1、2 的时候。
注意一点，如果直接递归返回值测试会出现超时，因为会重复计算前面的值，比如下面就会超时。
超时的案例
/**
* @param {number} n
* @return {number}
*/
var tribonacci = function (n) {
if (n === 0) return 0;
if (n === 1) return 1;
if (n === 2) return 1;
return tribonacci(n - 3) + tribonacci(n - 2) + tribonacci(n - 1);
};
合理的写法是将历史计算值做一个缓存，计算效率就会大大提高。
合理的写法
代码：
/**
* @param {number} n
* @return {number}
*/
var tribonacci = function (n) {
const cache = {};
return cal(n);
function cal(s) {
if (s === 0) return 0;
if (s === 1 || s === 2) return 1;
if (cache[s]) return cache[s];
cache[s] = cal(s - 3) + cal(s - 2) + cal(s - 1);
return cache[s];
}
};
解法二
思路：
滚动数组的思想
将 n 前面的三个数存起来，计算出和，再将和赋值到最后一个位置，依次循环，就可以把前面的数字全部累计相加了
代码：
/**
* @param {number} n
* @return {number}
*/
var tribonacci = function (n) {
if (n === 0) return 0;
if (n === 1 || n === 2) return 1;
let a = 0,
b = 1,
c = 1,
sum;
for (let i = 3; i <= n; i++) {
sum = a + b + c;
a = b;
b = c;
c = sum;
}
return sum;
};
评论