泰波那契序列 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    @functools.lru_cache()  
#在 python3 中，可以使用语言自带的「记忆化搜索」的注解：@functools.lru_cache()，
#它的用法只有一行，即在要执行记忆化的函数上面加上一行注解，即可在语言级别的自动化的记忆化递归。
#1.注意是在python3中使用，2.不加此语句会报超时
    def tribonacci(self, n: int) -> int:
        if n<2:
            return n
        if n==2:
            return 1
        return self.tribonacci(n-1)+self.tribonacci(n-2)+self.tribonacci(n-3)

class Solution(object):
    def tribonacci(self, n):
        """
        :type n: int
        :rtype: int
        """
        T=[0]*100
        T[0]=0
        T[1]=1
        T[2]=1
        for i in range(3,n+1):
            T[i]=T[i-1]+T[i-2]+T[i-3]
        return T[n]