The Tribonacci sequence Tn is defined as follows: 
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.
 
Example 1:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:
Input: n = 25
Output: 1389537

 
Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Difficulty: introductory

Starter code:

class Solution:
    def tribonacci(self, n: int) -> int:
        

Solutions:
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        ans = [0] * (n+1)
        ans[0] = 0 
        ans[1] = 1 
        ans[2] = 1 
        
        for i in range(3, n+1):
            ans[i] = ans[i-1] + ans[i-2] + ans[i-3]
        return ans[n]

class Solution:
    
        
       
        
        
    def tribonacci(self, n: int) -> int:
        
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        
        F = [0] * 38
        
        F[0] = 0
        F[1] = 1
        F[2] = 1
        
        for i in range(3,n+1):
            F[i] = F[i-1] + F[i-2] + F[i-3]
            
        return F[n]

from collections import deque 
class Solution:
    def tribonacci(self, n: int) -> int:
        if n>0 and n<3:
            return 1
        if n==0:
            return 0
        queue = deque([0,1,1])
        t = 2
        while t!=n:
            queue.append(sum(queue))
            queue.popleft()
            t+=1
        return queue[2]

class Solution:
    def tribonacci(self, n: int) -> int:
        T = [0, 1, 1]
        for n in range(3, n + 1):
            T.append(T[n - 3] + T[n - 2] + T[n - 1])
        return T[n]

class Solution:
    def tribonacci(self, n: int) -> int:
        trib = []
        trib.append(0)
        trib.append(1)
        trib.append(1)
        for i in range(3, n):
            trib.append(trib[i-1] + trib[i-2] + trib[i-3])
            
        if n > 2:
            return trib[n-1] + trib[n-2] + trib[n-3]
        else:
            return trib[n]


class Solution:
    trib = [0,1,1]
    def tribonacci(self, n: int) -> int:
        try:
            return self.trib[n]
        except:
            currlen = len(self.trib)
            for i in range(currlen,n+1):
                self.trib.append(self.trib[i-1]+self.trib[i-2]+self.trib[i-3])
            return self.trib[n]


class Solution:
    def tribonacci(self, n: int) -> int:
        if n<3:
            return 1 if n else 0
        
        nums = [0]*(n+1)
        nums[0]=0
        nums[1]=1
        nums[2]=1
        
        for i in range(3, n+1):
            nums[i]=nums[i-1]+nums[i-2]+nums[i-3]
            
        return nums[n]
        
        


class Solution:
    DP: List[int] = [0, 1, 1]
    
    def tribonacci(self, n: int) -> int:
        if n >= 0:
            if n < len(self.DP):
                return self.DP[n]
            else:
                offset: int = len(self.DP)
                self.DP.extend([0] * (n - offset + 1))
                for i in range(offset, n + 1):
                    self.DP[i] = self.DP[i - 3] + self.DP[i - 2] + self.DP[i - 1]
                return self.DP[n]
        else:
            raise ValueError


class Solution:
    def tribonacci(self, n: int) -> int:
        t = [0,1,1]
        if n < 3:
            return t[n]
        
        for i in range(n-2):
            t.append(sum(t))
            t = t[1:]
        
        return t[2]

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n < 3:
            return 1
        t0, t1, t2 = 0, 1, 1
        for _ in range(3, n+1):
            ans = t0 + t1 + t2
            t0, t1, t2 = t1, t2, ans
        return ans