N-th Tribonacci Number Solution - The Coding Shala

Home >> Programming >> N-th Tribonacci Number

Hey there, welcome back to another post. In this post, we will learn how to solve the N-th Tribonacci Number problem and will implement its solution in Java.

N-th Tribonacci Number

Problem Statement

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

N-th Tribonacci Number Java Solution using Bottom-Up DP

This problem is similar to the Fibonacci series. We can solve it using the Bottom-Up approach of dynamic programming.

Time Complexity: O(n)

Space Complexity: O(n)

The space complexity can be reduced to O(1) by using variables to store the previous three values instead of using an array.

Java Program:

```class Solution {
public int tribonacci(int n) {
if (n == 0) return 0;

if (n == 1 || n == 2) return 1;

int[] dp = new int[n+1];

// base cases
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;

for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}

return dp[n];
}
}
```

N-th Tribonacci Number Java Solution using Memoization

We can also solve this problem by using recursion and memoization or top-down dynamic programming.

Java Program:

```class Solution {
public int tribonacci(int n) {
Map<Integer, Integer> memo = new HashMap<>();
return rec(n, memo);
}

public int rec(int n, Map<Integer, Integer> memo) {
if (n == 0) return 0;
if(n == 1 || n == 2) return 1;

memo.put(0, 0);
memo.put(1, 1);
memo.put(2, 1);

if(memo.containsKey(n)) return memo.get(n);

int res = rec(n-1, memo) + rec(n-2, memo) + rec(n-3, memo);
memo.put(n, res);

return res;
}
}
```

Other Posts You May Like