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 = 1
int a = 0, b = 1, c = 1; // 分别对应 T0, T1, T2
int d = 0;
for (int i = 3; i <= n; ++i) {
d = a + b + c; // 计算 T_i
a = 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 0
if n <= 2:
return 1
a, b, c = 0, 1, 1 # 对应 T0, T1, T2
for _ in range(3, n + 1):
a, b, c = b, c, a + b + c
return 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)（递归栈 + 备忘录）
对于本题，方法一最为简洁高效，推荐使用滚动变量迭代。