LeetCode Notes: N-th Tribonacci Number

Question

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given `n`, return the value of Tn.

Example 1:

Input: n = 4

Output: 4

Explanation:

T_3 = 0 + 1 + 1 = 2

T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25

Output: 1389537

Constraints:

• `0 <= n <= 37`
• The answer is guaranteed to fit within a 32-bit integer, ie. `answer <= 2^31 - 1`.

Solution One

Analysis:

The idea of dynamic programming

The core code is the translation formula Tn+3 = Tn + Tn+1 + Tn+2 , and then deal with when the next three boundary values n are 0, 1, and 2.

Note that if you directly recurse the return value test, there will be a timeout, because the previous value will be repeatedly calculated, such as the following will timeout.

Timeout case

``````/**
* @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);
};
``````

A reasonable way of writing is to cache the historical calculation values, and the calculation efficiency will be greatly improved.

Reasonable code

Code:

``````/**
* @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];
}
};
``````

Solution Two

Analysis:

The idea of rolling arrays

Store the three numbers in front of `n`, calculate the sum, and then assign the sum to the last position, and loop in turn to add up all the previous numbers.

Code:

``````/**
* @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;
};
``````