2023-01-30.md

题目

1137. N-th Tribonacci Number

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.

思路

代码

// runtime 61.7% memory 63.27%
var tribonacci = function(n) {
  const t = [0, 1, 1]
  for (let i = 3; i <= n; i++) {
    t[i] = t[i-1] + t[i-2] + t[i-3]
  }
  return t[n]
}

// runtime 35.34% memory 95.37%
var tribonacci = function(n) {
  const t = [0, 1, 1]
  for (let i = 3; i <= n; i++) {
    t[i%3] = t[0] + t[1] + t[2]
  }
  return t[n%3]
}

// runtime 97.80% memory 81.23%
var tribonacci = function(n) {
  if (n < 2) {
    return n
  }
  let a = 0, b = 1, c = 1
  while (n-- > 2) {
    const d = a + b + c
    a = b
    b = c
    c = d
  }
  return c
}