1137.N-th Tribonacci Number

tags: Easy,Math,DP,Memoization

1137. N-th Tribonacci Number

題目描述

The Tribonacci sequence

$T_n$ is defined as follows:

$T_0$ = 0,

$T_1$ = 1,

$T_2$ = 1, and

$T_{n+3}$ =

$T_n$ +

$T_{n+1}$ +

$T_{n+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³¹ - 1.

解答

Javascript

function tribonacci(n) {
  const result = [0, 1, 1];
  for (let i = 3; i <= n; i++) {
    result[i] = result[i - 1] + result[i - 2] + result[i - 3];
  }

  return result[n];
}

Time:

$O(n)$
Space:

$O(n)$

function tribonacci2(n) {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;
    
  let a = 0;
  let b = 1;
  let c = 1;
  for (let i = 3; i <= n; i++) {
    [a, b, c] = [b, c, a + b + c];
  }

  return c;
}

Time:

$O(n)$
Space:

$O(1)$

JS可以直接這樣交換好方便！
MarsgoatJan 30, 2023

Python

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0: return 0
        if n == 1 or n == 2: return 1

        a, b, c = 1, 0, 0
        for _ in range(n):
            a, b, c = b, c, a + b + c

        return c

Ron ChenJan 30, 2023

Reference

回到題目列表