题目
https://leetcode-cn.com/problems/n-th-tribonacci-number/
解答：
# @TIME : 2019/11/1 上午8:06 # @File : 第 N 个泰波那契数_1137.py """ 泰波那契序列 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 <= 37 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。 """ import functools import time class Solution: def tribonacci(self, n: int) -> int: if n==0: return 0 if n==1: return 1 if n==2: return 1 return self.tribonacci(n-1)+self.tribonacci(n-2)+self.tribonacci(n-3) def tribonacci2(self, n: int) -> int: """空间换时间""" rel = [0, 1, 1] if n < 3: return rel[n] for i in range(3, n+1): rel.append(rel[i-3] + rel[i-2] + rel[i-1]) return rel[n] if __name__ == "__main__": t1 = time.time() A = Solution() rel = A.tribonacci(10) t2 = time.time() print(rel) print(t2 - t1) time.sleep(1) t3 = time.time() A = Solution() rel1 = A.tribonacci2(10) t4 = time.time() print(rel1) print(t4 - t3) 149 8.606910705566406e-05 149 4.410743713378906e-05
