1137. 第 N 个泰波那契数

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]
本站总访问量  次  |  您是本站第  位访问者