*Companies: Coursera*

The Tribonacci sequence `Tn`

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 Tn.

#### Example 1:

Input: n = 4

Output: 4

Explanation:

T_3 = 0 + 1 + 1 = 2

T_4 = 1 + 1 + 2 = 4

#### Example 2:

**Constraints:**

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

.

### Solution:

There can be two possible scenerios to implement the solution: 1. Space Optimisation, 2. Performance Optimisation.

Space Optimisation can be implementated using dynamic programming without using recursion in it.

We will implement second type of optimisation here:

Performance based Optimisation. We will use both dynamic programming as well as recursion.

Dynamic Programming has two major categories: Memoization and Tabulation.

Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.

We will use precomputed 38 Tribonacci numbers:

- Initialize an array of Tribonacci numbers of size 38 with
`0`

. - Return tribo(n-1).

The next is Recursion:

- if
`k = 0`

, return`0`

. - If
`nums[k] != 0`

, return`nums[k]`

. - Otherwise,
`nums[k] = tribo(k - 1) + tribo(k - 2) + tribo(k - 3)`

. Return nums[k].

### Implementation

#### Java

class Tri { private int n = 38; public int[] nums = new int[n]; int tribo(int k) { if (k == 0) return 0; if (nums[k] != 0) return nums[k]; nums[k] = tribo(k - 1) + tribo(k - 2) + tribo(k - 3); return nums[k]; } Tri() { nums[1] = 1; nums[2] = 1; tribo(n - 1); } } class Solution { public static Tri t = new Tri(); public int tribonacci(int n) { return t.nums[n]; } }

### Complexity Analysis:

**Time Complexity:**O(1).**Space Complexity:**Constant Space.