leetcode 1137 第n个泰波那契数
leetcode 1137 第n个泰波那契数
什么是泰波那契数
泰波那契数（Tribonacci numbers）是类似于斐波那契数列的数列，但不同之处在于泰波那契数列中的每一项是之前三项的和，而不是前两项的和。
公式
t n = t n − 1 + t n − 2 + t n − 3 t_n = t_{n-1} + t_{n-2} + t_{n-3} tn=tn−1+tn−2+tn−3
思路
从公式里面可以看到tn 是通过前三位数进行相加来的，所以可以创建一个dp数组。每个下标的内容就是当前下表对应的值。
我们需要先把前三位的值给写出来，因为后面的是需要根据前面的来进行计算。
具体请看代码。
代码
function tribonacci(n: number): number {
const dp = new Array(n + 1).fill(0);
dp[0] = 0;
dp[1] = 1
dp[2] = 1
for (let i = 3; i < n + 1; i++) {
dp[i] = dp[i] + dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
console.log(tribonacci(25))
结语
如果对您有帮助的话，您可以搜搜一下正在努力的迪迦关注一下此公众号吗？谢谢您了。