难度: Easy
泰波那契序列 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 <= 37answer <= 2^31 - 1。运行时间: 18 ms
内存: 16.0 MB
class Solution:
def tribonacci(self, n: int) -> int:
T0,T1,T2=0,1,1
if n==0:
return 0
elif n==1 or n==2:return 1
for i in range(3,n+1):
s=T1+T2+T0
T0,T1,T2=T1,T2,s
# print(T0,T1,T2)
return s
此题解采用迭代方法计算泰波那契数。首先初始化前三个泰波那契数 T0 = 0, T1 = 1, T2 = 1。针对 n 分别小于等于 0, 1, 2 的情况直接返回对应的泰波那契数值。对于 n 大于 2 的情况，使用一个 for 循环从 3 迭代到 n。在每次迭代中，计算当前泰波那契数为前三个数的和，然后更新这三个数，即使得 T0 = T1, T1 = T2, T2 = 新计算的和。最终，循环结束后返回 T2，即第 n 个泰波那契数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def tribonacci(self, n: int) -> int:
# 初始化第0、1、2个泰波那契数
T0, T1, T2 = 0, 1, 1
# 针对特定小值直接返回结果
if n == 0:
return 0
elif n == 1 or n == 2:
return 1
# 从第3个数开始迭代计算到第n个数
for i in range(3, n + 1):
s = T1 + T2 + T0 # 计算当前泰波那契数
T0, T1, T2 = T1, T2, s # 更新三个数
# print(T0, T1, T2) # 可用于调试查看每步的值
return s # 返回第n个泰波那契数
直接返回 n=0, n=1 和 n=2 的情况是为了简化代码和提高效率。因为这三个条件是泰波那契数列的基础情况，对它们的值已经确定（T0=0, T1=1, T2=1），不需要任何计算。如果将这些情况包含在迭代循环中，循环将执行不必要的迭代，因此，处理这些特殊情况可以避免不必要的计算并提高程序的执行速度。
这种更新方式不会影响计算的准确性，因为每次迭代都正确地计算了泰波那契数的值，并按照预期更新了T0, T1, T2的值。从执行效率的角度看，这种更新方式是高效的，因为它仅使用有限的变量并在单个循环中完成所有操作，避免了额外的内存分配或不必要的计算。
迭代方法的优势在于它通常具有更高的时间效率和更低的空间复杂度，因为它避免了递归调用栈的开销。迭代方法只使用固定数量的变量，而递归方法可能因为深度递归调用而导致栈溢出。然而，递归方法的代码通常更简洁易懂，尤其是在逻辑上直接模拟数学定义的情况下。迭代方法在理解和维护上可能稍微复杂一些，但在执行上通常更优。
是的，给定 n 的最大值为 37，迭代方法在这种情况下的性能是完全可接受的。迭代方法因其简单和直接，能够快速计算出第 n 个泰波那契数，且不会占用过多的内存或处理时间。这使得迭代方法非常适合解决这类问题，特别是在问题的规模较小且明确定义的情况下。