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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala