【算法】动态规划：1137. 第 N 个泰波那契数

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)（递归栈 + 备忘录）

---

对于本题，方法一最为简洁高效，推荐使用滚动变量迭代。