The Tribonacci sequence Tn is defined as follows:&nbsp;

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n &gt;= 0.

Given n, return the value of Tn.

&nbsp;
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


&nbsp;
Constraints:


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

class Solution:
    def tribonacci(self, n: int, q={}) -> int:
        if n<3:
            q[0]=0 #Initialize first 3 values 
            q[1]=1
            q[2]=1
        if n not in q:  #Have faith that last 3 calls will give the answer :)
            q[n]=self.tribonacci(n-1,q)+self.tribonacci(n-2,q)+self.tribonacci(n-3,q)
        return q[n]
class Solution {
    public int tribonacci(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        if(n==2)
            return 1;
        int p1=1;
        int p2=1;
        int p3=0;
        int cur=0;
        for(int i=3;i<=n;i++)
        {
            cur=p1+p2+p3;
            p3=p2;
            p2=p1;
            p1=cur;
        }
        return cur;
    }
}
class Solution {
public:
    int tribonacci(int n) {
        if(n<2)
            return n;
        
        int prev3 = 0;
        int prev2 = 1;
        int prev1 = 1;
        
        for(int i = 3; i<= n ; i++)
        {
            int ans  = prev1+ prev2+prev3;
            prev3 = prev2;
            prev2 = prev1;
            prev1 = ans;
        }
        
        return prev1;
    }
};
// Recursive and Memoiztion approach
var tribonacci = function(n, cache = {}) {
    if(n in cache) return cache[n]

    //Start of Base Cases
    if(n == 0) return 0
    if (n == 1 || n == 2) return 1;
    // End Of Base Cases
    
    // Caching the result
    cache[n] = tribonacci(n - 1, cache) + tribonacci(n - 2, cache) + tribonacci(n - 3, cache);
    
    return cache[n]; 
};

// Tabulation Approach
var tribonacci = function(n) {
    // Create the Table;
    const table = Array(n + 1).fill(0);
    table[1] = 1;
    for(let i =0;i<=n;i++){
        //Iterate over the table and increase the values respectively
        table[i+1] += table[i]
        table[i+2] += table[i]
        table[i+3] += table[i]
    }
    return table[n]
};
N-th Tribonacci Number