1137. 第 N 个泰波那契数 - 力扣（LeetCode）

解法 1：递归（O(3^n)，不推荐）

递归直接按照数学定义实现，但时间复杂度高，不适合大 n。

class Solution:def tribonacci(self, n: int) -> int:if n == 0:return 0elif n == 1 or n == 2:return 1return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)

缺点：大量重复计算，时间复杂度 O(3^n)，n 较大时会超时。

解法 2：动态规划（O(n)，空间 O(n)）

使用数组存储计算结果，按顺序计算。

class Solution:def tribonacci(self, n: int) -> int:if n == 0:return 0if n == 1 or n == 2:return 1dp = [0] * (n + 1)dp[1] = dp[2] = 1for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]return dp[n]

✅ 优点：时间复杂度 O(n)，比递归更快。
⚠️ 缺点：空间复杂度 O(n)。

解法 3：迭代（O(n)，空间 O(1)）

只存储 前三个变量，减少空间占用。

class Solution:def tribonacci(self, n: int) -> int:if n == 0:return 0if n == 1 or n == 2:return 1a, b, c = 0, 1, 1for _ in range(n - 2):a, b, c = b, c, a + b + creturn c

✅ 优点：时间复杂度 O(n)，空间复杂度 O(1)，适合大 n。