1137.N-th Tribonacci Number
===

###### tags: `Easy`,`Math`,`DP`,`Memoization`

[1137. N-th Tribonacci Number](https://leetcode.com/problems/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^31^ - 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可以直接這樣交換好方便！
> [name=Marsgoat][time=Jan 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

> [name=Ron Chen][time=Jan 30, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)