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]