1137. 第 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}$ 的值。

解题思路 #

因为 0 <= n <= 37，所以我们可以先递推求出 37 个泰波那契数的值，然后用数组存储起来。最后直接输出即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Preprocess:
    def __init__(self):
        n = 38
        self.nums = nums = [0] * n
        nums[1] = nums[2] = 1
        for i in range(3, n):
            nums[i] = nums[i - 1] + nums[i - 2] + nums[i - 3]

class Solution:
    pre = Preprocess()
    def tribonacci(self, n: int) -> int:
        return self.pre.nums[n]