【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++