1137. 第 N 個泰波那契數
簡單
相關標簽
premium lock icon
相關企業
提示
泰波那契序列 Tn 定義如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的條件下 Tn+3 = Tn + Tn+1 + Tn+2
給你整數 n，請返回第 n 個泰波那契數 Tn 的值。
示例 1：
輸入：n = 4
輸出：4
解釋：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
輸入：n = 25
輸出：1389537
提示：
0 <= n <= 37
答案保證是一個 32 位整數，即 answer <= 2^31 - 1。
分析
解題思路
泰波那契數列（Tribonacci）定義：
T? = 0,
T? = 1,
T? = 1,
T? = T??? + T??? + T??? （n ≥ 3）
我們要計算第 n 項 T?。由于 n ≤ 37，直接用動態規劃即可在 O(n) 時間內完成，且可以只用 O(1) 的額外空間（滾動變量）。
方法一：迭代 + 滾動變量（空間 O(1)）
維護三個變量 a=T???、b=T???、c=T???，從 i=3 迭代到 n，每次計算 d = a + b + c，然后滾動更新：
// C++ 實現
class Solution {
public:int tribonacci(int n) {if (n == 0) return 0;if (n <= 2) return 1; // T1 = T2 = 1int a = 0, b = 1, c = 1; // 分別對應 T0, T1, T2int d = 0;for (int i = 3; i <= n; ++i) {d = a + b + c; // 計算 T_ia = b; // 滾動：下輪 a = T_{i-2}b = c; // b = T_{i-1}c = d; // c = T_i}return c;}
};
# Python 實現
class Solution:def tribonacci(self, n: int) -> int:if n == 0:return 0if n <= 2:return 1a, b, c = 0, 1, 1 # 對應 T0, T1, T2for _ in range(3, n + 1):a, b, c = b, c, a + b + creturn c
- 時間復雜度：O(n)
- 空間復雜度：O(1)
方法二：遞歸 + 備忘錄（空間 O(n)）
雖然遞歸更直觀，但不加緩存會產生大量重復子問題。使用哈希表或數組保存已計算的 T?：
// C++ 實現：遞歸 + 備忘錄
class Solution {vector<int> memo;
public:int tribonacci(int n) {memo.assign(n+1, -1);return dfs(n);}int dfs(int i) {if (i == 0) return 0;if (i <= 2) return 1;if (memo[i] != -1) return memo[i];return memo[i] = dfs(i-1) + dfs(i-2) + dfs(i-3);}
};
# Python 實現：遞歸 + 備忘錄
class Solution:def __init__(self):self.memo = {0: 0, 1: 1, 2: 1}def tribonacci(self, n: int) -> int:if n in self.memo:return self.memo[n]self.memo[n] = (self.tribonacci(n-1)+ self.tribonacci(n-2)+ self.tribonacci(n-3))return self.memo[n]
- 時間復雜度：O(n)
- 空間復雜度：O(n)（遞歸棧 + 備忘錄）
對于本題，方法一最為簡潔高效，推薦使用滾動變量迭代。
