### N-th Tribonacci Number Solution - The Coding Shala

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

- Fibonacci Series
- Universal Solution of Single Number Problem
- Power of Two
- Hamming Distance
- Simple XML Validator

## Comments

## Post a Comment