The Tribonacci sequence T_{n} is defined as follows:

T_{0} = 0, T_{1} = 1, T_{2} = 1, and T_{n+3} = T_{n} + T_{n+1} + T_{n+2} for n >= 0.

GivenĀ `n`

, return the value of T_{n}.

```
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
```

```
class Solution {
public int tribonacci(int n) {
if (n <= 1) {
return n;
}
if (n ==2){
return 1;
}
int cache[] = new int [n+1];
cache[1] = 1;
cache[2] = 1;
for(int i=3;i<=n;i++) {
cache[i] = cache[i-1] + cache[i-2] + cache[i-3];
}
return cache[n];
}
}
```