泰波那契数列题解

听说过斐波那契数列,那你听说过泰波那契数列吗?

上题!

泰波那契序列 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​​。

第一反应

斐波那契是 T(n) = T(n-1) + T(n-2)

泰波那契是 T(n) = T(n-1) + T(n-2) + T(n-3)

那求和也简单鸭,第一个数是 0,第二个数是 1,第三个数是 2

var tribonacci = function(n) {
let x = 0
let y = 1
let z = 1
let res = 0
if(n<2) return n
if(n==2) return 1
for(let i=3;i<=n;i++){
res = x+y+z
x = y
y = z
z = res
}
return res
};

第二反应

递归求解

var tribonacci = function(n) {
let x = 0
let y = 1
let z = 1
if(n<2) return n
if(n==2) return 1
let res = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)
return res
};

泰波那契数列题解

运行时间超出内存,递归时间复杂度 O(3n)

小结:

本题关键在于认识下泰波那契数,有概念即可~~

是不是对于斐波那契、爬楼梯这样的题目得心应手了呢?(●'◡'●)

OK,以上便是本篇分享。点赞关注评论,为好文助力?

发表评论

相关文章