本文共 1020 字，大约阅读时间需要 3 分钟。

泰波那契序列$T_n$定义如下：

$T_0 = 0, T_1 = 1, T_2 = 1, $且在‘n>=0‘的条件下$T_{n+3} = T_n + T_{n+1} + T_{n+2}$

给你整数 n，请返回第n个泰波那契数$T_n$的值。

示例 1：

输入：n = 4输出：4解释：T_3 = 0 + 1 + 1 = 2T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25输出：1389537

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

解题思路

计算第 N 个泰波那契数非常简单，我这里使用python yield实现。

def tri(x):    n, a, b, c = 0, 0, 1, 1    while n < x:        yield a + b + c        a, b, c = b, c, a + b + c        n += 1

因为n最大是32，所以我们可以先把所有的数给算出来，然后只要对输入的数在字典中查询即可。

class Solution:    d = dict()    def tribonacci(self, n: int) -> int:        def tri(x):            n, a, b, c = 0, 0, 1, 1            while n < x:                yield a + b + c                a, b, c = b, c, a + b + c                n += 1                        if n in self.d:            return self.d[n]                for i, v in enumerate(tri(35)):            self.d[i + 3] = v        self.d[0], self.d[1], self.d[2] = 0, 1, 1        return self.d[n]

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/97623712 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！