 # Nth Tribonacci Number

Problem Source

Companies: Coursera

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:

Constraints:

1. 0 <= n <= 37
2. 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:

1. Initialize an array of Tribonacci numbers of size 38 with `0`.
2. 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;
nums = 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.
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.