LeetCode Notes: N-th Tribonacci Number

#leetcode

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;
};

Reference

Comments