# 【LeetCode】 1137. N-th Tribonacci Number

## Description
> 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.

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

> Tribonacci 數列中 Tn 的定義如下：
> T0 = 0, T1 = 1, T2 = 1, 且 Tn+3 = Tn + Tn+1 + Tn+2 在 n >= 0 時。
> 給予 `n`，回傳 Tn 的值。

> 限制：
> 0 <= n <= 37
> 答案保證在 32-bit 的整數之中，也就是說答案 <= 2^31 - 1。

## Example:

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

## Solution

* 費波納西數列的變種題目，也就是遞迴的經典題
* 基本上就是將定義中的 `0` `1` `2` 遇到時直接回傳，其他則是利用遞迴去找答案
* 值得注意的是超時 (TLE) 的問題，當今天數字很大的時候，會有過多重複計算的部分
* 例如 tribonacci(37) = t(36) + t(35) + t(34)
* 而 t(36) = t(35) + t(34) + t(33)
* 此時你會發現 t(35) 在 37 時已經算過一次，在 36 時又需要計算一次
* 如何解決？直接用一個表去記錄所有已經跑過的值即可

### Code

class Solution {
public:
    int table[40];
    int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 1;
        if(table[n] != 0) return table[n];
        table[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
        return table[n];
    }
};

###### tags: `LeetCode` `C++`