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

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

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.