Posted on by Kalkicode
Code Dynamic Programming

Tribonacci triangle

In this article, we will explore the concept of a Tribonacci triangle. We will discuss the problem statement, the algorithm to solve it, and provide a solution in C programming language. Additionally, we will analyze the time complexity of the code.

Introduction

The Tribonacci triangle is a triangular arrangement of numbers where each row represents the Tribonacci sequence. The Tribonacci sequence is similar to the Fibonacci sequence, but instead of adding the previous two numbers, it adds the previous three numbers to generate the next number. The Tribonacci sequence starts with 0, 0, 1, and each subsequent number is the sum of the previous three numbers.

Problem Statement

The problem is to print the Tribonacci triangle with a given number of rows, denoted by 'n'. Each row of the triangle represents the Tribonacci sequence up to that row.

Algorithm

To solve this problem, we can use dynamic programming to optimize space complexity. The following algorithm outlines the steps:

  1. Check if the given number of rows, 'n', is valid. If it is less than or equal to 0, return.
  2. Create a 2D array, 'dp', with 2 rows and 'n+1' columns to store the triangle values.
  3. Set the initial values of the first column in both rows to 1.
  4. Initialize a variable 'row' to 0 to keep track of the current row.
  5. Use a nested loop to iterate through each column and row of the triangle:
    • Set the initial value in the current column to 0.
    • For each column, calculate the Tribonacci value based on the previous values in the triangle.
    • Print each Tribonacci value as it is calculated.
    • Update the 'back' variable to store the previous value before calculating the next one.
  6. After completing a row, set the 'back' variable to 1 to prepare for the next row.
  7. Switch the 'row' variable between 0 and 1 to alternate between rows.

Code Solution

// C Program for
// Tribonacci triangle
#include <stdio.h>

void tribonacciTriangle(int n)
{
	if (n <= 0)
	{
		return;
	}
	// Optimize N *N space by using 2 rows and n+1 columns
	int dp[2][n + 1];
	// Set initial value of first column
	dp[0][0] = 1;
	dp[1][0] = 1;
	// We can solve this problem only use two rows
	// So initial select first row which position is 0
	int row = 0;
	// Auxiliary variables
	int temp = 0;
	int back = 0;
	for (int i = 1; i <= n; ++i)
	{
		// Set initial value in current column
		dp[0][i] = 0;
		dp[1][i] = 0;
		for (int j = 0; j < i; ++j)
		{
			if (j > 0)
			{
				if (j + 1 == i)
				{
					// When last element
					dp[row][j] = 1;
				}
				else if (row == 1)
				{
					temp = dp[row][j];
					// Change second row 'j' column value
					// Combination of three elements
					dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
					back = temp;
				}
				else
				{
					temp = dp[row][j];
					// Change first row 'j' column value
					// Combination of three elements
					dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
					back = temp;
				}
			}
			printf("  %d", dp[row][j]);
		}
		back = 1;
		printf("\n");
		if (i > 1)
		{
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
}
int main()
{
	/*
	                           1
	                        1     1
	                     1     3     1
	                  1     5     5     1
	               1     7     13    7     1
	            1     9     25    25    9     1
	         1     11    41    63    41    11    1
	      1     13     61   129   129   61    13    1
	    1    15     85   231   321   231   85    15    1
	  1    17   113   377    681   681  377   113   17   1
	  ------------------------------------------------------
	*/
	tribonacciTriangle(10);
	return 0;
}

Output

  1
  1  1
  1  3  1
  1  5  5  1
  1  7  13  7  1
  1  9  25  25  9  1
  1  11  41  63  41  11  1
  1  13  61  129  129  61  13  1
  1  15  85  231  321  231  85  15  1
  1  17  113  377  681  681  377  113  17  1
// Java program for
// Tribonacci triangle
public class Triangle
{
	public void tribonacciTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows and n+1 columns
		int[][] dp = new int[2][n + 1];
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select first row which position is 0
		int row = 0;
		// Auxiliary variables
		int temp = 0;
		int back = 0;
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0][i] = 0;
			dp[1][i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						temp = dp[row][j];
						// Change second row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
						back = temp;
					}
					else
					{
						temp = dp[row][j];
						// Change first row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
						back = temp;
					}
				}
				System.out.print(" " + dp[row][j]);
			}
			back = 1;
			System.out.print("\n");
			if (i > 1)
			{
				if (row == 1)
				{
					row = 0;
				}
				else
				{
					row = 1;
				}
			}
		}
	}
	public static void main(String[] args)
	{
		Triangle task = new Triangle();
		/*
		                               1
		                            1     1
		                         1     3     1
		                      1     5     5     1
		                   1     7     13    7     1
		                1     9     25    25    9     1
		             1     11    41    63    41    11    1
		          1     13     61   129   129   61    13    1
		        1    15     85   231   321   231   85    15    1
		      1    17   113   377    681   681  377   113   17   1
		    ----------------------------------------------------------
		*/
		task.tribonacciTriangle(10);
	}
}

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1
// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Tribonacci triangle
class Triangle
{
	public: void tribonacciTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows and n+1 columns
		int dp[2][n + 1];
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select first row which position is 0
		int row = 0;
		// Auxiliary variables
		int temp = 0;
		int back = 0;
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0][i] = 0;
			dp[1][i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						temp = dp[row][j];
						// Change second row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
						back = temp;
					}
					else
					{
						temp = dp[row][j];
						// Change first row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
						back = temp;
					}
				}
				cout << " " << dp[row][j];
			}
			back = 1;
			cout << "\n";
			if (i > 1)
			{
				if (row == 1)
				{
					row = 0;
				}
				else
				{
					row = 1;
				}
			}
		}
	}
};
int main()
{
	Triangle *task = new Triangle();
	/*
	                               1
	                            1     1
	                         1     3     1
	                      1     5     5     1
	                   1     7     13    7     1
	                1     9     25    25    9     1
	             1     11    41    63    41    11    1
	          1     13     61   129   129   61    13    1
	        1    15     85   231   321   231   85    15    1
	      1    17   113   377    681   681  377   113   17   1
	    ----------------------------------------------------------
	*/
	task->tribonacciTriangle(10);
	return 0;
}

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1
// Include namespace system
using System;
// Csharp program for
// Tribonacci triangle
public class Triangle
{
	public void tribonacciTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows and n+1 columns
		int[,] dp = new int[2,n + 1];
		// Set initial value of first column
		dp[0,0] = 1;
		dp[1,0] = 1;
		// We can solve this problem only use two rows
		// So initial select first row which position is 0
		int row = 0;
		// Auxiliary variables
		int temp = 0;
		int back = 0;
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0,i] = 0;
			dp[1,i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row,j] = 1;
					}
					else if (row == 1)
					{
						temp = dp[row,j];
						// Change second row 'j' column value
						// Combination of three elements
						dp[row,j] = dp[0,j] + dp[0,j - 1] + back;
						back = temp;
					}
					else
					{
						temp = dp[row,j];
						// Change first row 'j' column value
						// Combination of three elements
						dp[row,j] = dp[1,j] + dp[1,j - 1] + back;
						back = temp;
					}
				}
				Console.Write(" " + dp[row,j]);
			}
			back = 1;
			Console.Write("\n");
			if (i > 1)
			{
				if (row == 1)
				{
					row = 0;
				}
				else
				{
					row = 1;
				}
			}
		}
	}
	public static void Main(String[] args)
	{
		Triangle task = new Triangle();
		/*
		                               1
		                            1     1
		                         1     3     1
		                      1     5     5     1
		                   1     7     13    7     1
		                1     9     25    25    9     1
		             1     11    41    63    41    11    1
		          1     13     61   129   129   61    13    1
		        1    15     85   231   321   231   85    15    1
		      1    17   113   377    681   681  377   113   17   1
		    ----------------------------------------------------------
		*/
		task.tribonacciTriangle(10);
	}
}

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1
package main
import "fmt"
// Go program for
// Tribonacci triangle

func tribonacciTriangle(n int) {
	if n <= 0 {
		return
	}
	// Optimize N *N space by using 2 rows and n+1 columns
	var dp = make([][] int, 2)
	for i := 0; i < 2; i++ {
		dp[i] = make([]int,n+1)
	}
	// Set initial value of first column
	dp[0][0] = 1
	dp[1][0] = 1
	// We can solve this problem only use two rows
	// So initial select first row which position is 0
	var row int = 0
	// Auxiliary variables
	var temp int = 0
	var back int = 0
	for i := 1 ; i <= n ; i++ {
		// Set initial value in current column
		dp[0][i] = 0
		dp[1][i] = 0
		for j := 0 ; j < i ; j++ {
			if j > 0 {
				if j + 1 == i {
					// When last element
					dp[row][j] = 1
				} else if row == 1 {
					temp = dp[row][j]
					// Change second row 'j' column value
					// Combination of three elements
					dp[row][j] = dp[0][j] + dp[0][j - 1] + back
					back = temp
				} else {
					temp = dp[row][j]
					// Change first row 'j' column value
					// Combination of three elements
					dp[row][j] = dp[1][j] + dp[1][j - 1] + back
					back = temp
				}
			}
			fmt.Print(" ", dp[row][j])
		}
		back = 1
		fmt.Print("\n")
		if i > 1 {
			if row == 1 {
				row = 0
			} else {
				row = 1
			}
		}
	}
}
func main() {

	/*
	                               1
	                            1     1
	                         1     3     1
	                      1     5     5     1
	                   1     7     13    7     1
	                1     9     25    25    9     1
	             1     11    41    63    41    11    1
	          1     13     61   129   129   61    13    1
	        1    15     85   231   321   231   85    15    1
	      1    17   113   377    681   681  377   113   17   1
	    ----------------------------------------------------------
	*/
	tribonacciTriangle(10)
}

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1
<?php
// Php program for
// Tribonacci triangle
class Triangle
{
	public	function tribonacciTriangle($n)
	{
		if ($n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows and n+1 columns
		$dp = array_fill(0, 2, array_fill(0, $n + 1, 0));
		// Set initial value of first column
		$dp[0][0] = 1;
		$dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select first row which position is 0
		$row = 0;
		// Auxiliary variables
		$temp = 0;
		$back = 0;
		for ($i = 1; $i <= $n; ++$i)
		{
			for ($j = 0; $j < $i; ++$j)
			{
				if ($j > 0)
				{
					if ($j + 1 == $i)
					{
						// When last element
						$dp[$row][$j] = 1;
					}
					else if ($row == 1)
					{
						$temp = $dp[$row][$j];
						// Change second row 'j' column value
						// Combination of three elements
						$dp[$row][$j] = $dp[0][$j] + $dp[0][$j - 1] + $back;
						$back = $temp;
					}
					else
					{
						$temp = $dp[$row][$j];
						// Change first row 'j' column value
						// Combination of three elements
						$dp[$row][$j] = $dp[1][$j] + $dp[1][$j - 1] + $back;
						$back = $temp;
					}
				}
				echo(" ".$dp[$row][$j]);
			}
			$back = 1;
			echo("\n");
			if ($i > 1)
			{
				if ($row == 1)
				{
					$row = 0;
				}
				else
				{
					$row = 1;
				}
			}
		}
	}
}

function main()
{
	$task = new Triangle();
	/*
			                               1
			                            1     1
			                         1     3     1
			                      1     5     5     1
			                   1     7     13    7     1
			                1     9     25    25    9     1
			             1     11    41    63    41    11    1
			          1     13     61   129   129   61    13    1
			        1    15     85   231   321   231   85    15    1
			      1    17   113   377    681   681  377   113   17   1
			    ----------------------------------------------------------
			*/
	$task->tribonacciTriangle(10);
}
main();

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1
// Node JS program for
// Tribonacci triangle
class Triangle
{
	tribonacciTriangle(n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows and n+1 columns
		var dp = Array(2).fill(0).map(() => new Array(n + 1).fill(0));
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select first row which position is 0
		var row = 0;
		// Auxiliary variables
		var temp = 0;
		var back = 0;
		for (var i = 1; i <= n; ++i)
		{
			for (var j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						temp = dp[row][j];
						// Change second row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
						back = temp;
					}
					else
					{
						temp = dp[row][j];
						// Change first row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
						back = temp;
					}
				}
				process.stdout.write(" " + dp[row][j]);
			}
			back = 1;
			process.stdout.write("\n");
			if (i > 1)
			{
				if (row == 1)
				{
					row = 0;
				}
				else
				{
					row = 1;
				}
			}
		}
	}
}

function main()
{
	var task = new Triangle();
	/*
	                               1
	                            1     1
	                         1     3     1
	                      1     5     5     1
	                   1     7     13    7     1
	                1     9     25    25    9     1
	             1     11    41    63    41    11    1
	          1     13     61   129   129   61    13    1
	        1    15     85   231   321   231   85    15    1
	      1    17   113   377    681   681  377   113   17   1
	    ----------------------------------------------------------
	*/
	task.tribonacciTriangle(10);
}
main();

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1
#  Python 3 program for
#  Tribonacci triangle
class Triangle :
	def tribonacciTriangle(self, n) :
		if (n <= 0) :
			return
		
		#  Optimize N *N space by using 2 rows and n+1 columns
		dp = [[0] * (n + 1) for _ in range(2) ]
		#  Set initial value of first column
		dp[0][0] = 1
		dp[1][0] = 1
		#  We can solve this problem only use two rows
		#  So initial select first row which position is 0
		row = 0
		#  Auxiliary variables
		temp = 0
		back = 0
		i = 1
		while (i <= n) :
			j = 0
			while (j < i) :
				if (j > 0) :
					if (j + 1 == i) :
						#  When last element
						dp[row][j] = 1
					elif (row == 1) :
						temp = dp[row][j]
						#  Change second row 'j' column value
						#  Combination of three elements
						dp[row][j] = dp[0][j] + dp[0][j - 1] + back
						back = temp
					else :
						temp = dp[row][j]
						#  Change first row 'j' column value
						#  Combination of three elements
						dp[row][j] = dp[1][j] + dp[1][j - 1] + back
						back = temp
					
				
				print(" ", dp[row][j], end = "")
				j += 1
			
			back = 1
			print(end = "\n")
			if (i > 1) :
				if (row == 1) :
					row = 0
				else :
					row = 1
				
			
			i += 1
		
	

def main() :
	task = Triangle()
	#                               1
	#                            1     1
	#                         1     3     1
	#                      1     5     5     1
	#                   1     7     13    7     1
	#                1     9     25    25    9     1
	#             1     11    41    63    41    11    1
	#          1     13     61   129   129   61    13    1
	#        1    15     85   231   321   231   85    15    1
	#      1    17   113   377    681   681  377   113   17   1
	#    ----------------------------------------------------------
	task.tribonacciTriangle(10)

if __name__ == "__main__": main()

Output

  1
  1  1
  1  3  1
  1  5  5  1
  1  7  13  7  1
  1  9  25  25  9  1
  1  11  41  63  41  11  1
  1  13  61  129  129  61  13  1
  1  15  85  231  321  231  85  15  1
  1  17  113  377  681  681  377  113  17  1
#  Ruby program for
#  Tribonacci triangle
class Triangle 
	def tribonacciTriangle(n) 
		if (n <= 0) 
			return
		end

		#  Optimize N *N space by using 2 rows and n+1 columns
		dp = Array.new(2) {Array.new(n + 1) {0}}
		#  Set initial value of first column
		dp[0][0] = 1
		dp[1][0] = 1
		#  We can solve this problem only use two rows
		#  So initial select first row which position is 0
		row = 0
		#  Auxiliary variables
		temp = 0
		back = 0
		i = 1
		while (i <= n) 
			j = 0
			while (j < i) 
				if (j > 0) 
					if (j + 1 == i) 
						#  When last element
						dp[row][j] = 1
					elsif (row == 1) 
						temp = dp[row][j]
						#  Change second row 'j' column value
						#  Combination of three elements
						dp[row][j] = dp[0][j] + dp[0][j - 1] + back
						back = temp
					else
 
						temp = dp[row][j]
						#  Change first row 'j' column value
						#  Combination of three elements
						dp[row][j] = dp[1][j] + dp[1][j - 1] + back
						back = temp
					end

				end

				print(" ", dp[row][j])
				j += 1
			end

			back = 1
			print("\n")
			if (i > 1) 
				if (row == 1) 
					row = 0
				else
 
					row = 1
				end

			end

			i += 1
		end

	end

end

def main() 
	task = Triangle.new()
	#                               1
	#                            1     1
	#                         1     3     1
	#                      1     5     5     1
	#                   1     7     13    7     1
	#                1     9     25    25    9     1
	#             1     11    41    63    41    11    1
	#          1     13     61   129   129   61    13    1
	#        1    15     85   231   321   231   85    15    1
	#      1    17   113   377    681   681  377   113   17   1
	#    ----------------------------------------------------------
	task.tribonacciTriangle(10)
end

main()

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1
// Scala program for
// Tribonacci triangle
class Triangle()
{
	def tribonacciTriangle(n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows and n+1 columns
		var dp: Array[Array[Int]] = Array.fill[Int](2, n + 1)(0);
		// Set initial value of first column
		dp(0)(0) = 1;
		dp(1)(0) = 1;
		// We can solve this problem only use two rows
		// So initial select first row which position is 0
		var row: Int = 0;
		// Auxiliary variables
		var temp: Int = 0;
		var back: Int = 0;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp(row)(j) = 1;
					}
					else if (row == 1)
					{
						temp = dp(row)(j);
						// Change second row 'j' column value
						// Combination of three elements
						dp(row)(j) = dp(0)(j) + dp(0)(j - 1) + back;
						back = temp;
					}
					else
					{
						temp = dp(row)(j);
						// Change first row 'j' column value
						// Combination of three elements
						dp(row)(j) = dp(1)(j) + dp(1)(j - 1) + back;
						back = temp;
					}
				}
				print(" " + dp(row)(j));
				j += 1;
			}
			back = 1;
			print("\n");
			if (i > 1)
			{
				if (row == 1)
				{
					row = 0;
				}
				else
				{
					row = 1;
				}
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Triangle = new Triangle();
		/*
		                               1
		                            1     1
		                         1     3     1
		                      1     5     5     1
		                   1     7     13    7     1
		                1     9     25    25    9     1
		             1     11    41    63    41    11    1
		          1     13     61   129   129   61    13    1
		        1    15     85   231   321   231   85    15    1
		      1    17   113   377    681   681  377   113   17   1
		    ----------------------------------------------------------
		*/
		task.tribonacciTriangle(10);
	}
}

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1
// Swift 4 program for
// Tribonacci triangle
class Triangle
{
	func tribonacciTriangle(_ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows and n+1 columns
		var dp: [
			[Int]
		] = Array(repeating: Array(
                  repeating: 0, count: n + 1), count: 2
      );
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select first row which position is 0
		var row: Int = 0;
		// Auxiliary variables
		var temp: Int = 0;
		var back: Int = 0;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						temp = dp[row][j];
						// Change second row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
						back = temp;
					}
					else
					{
						temp = dp[row][j];
						// Change first row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
						back = temp;
					}
				}
				print(" ", dp[row][j], terminator: "");
				j += 1;
			}
			back = 1;
			print(terminator: "\n");
			if (i > 1)
			{
				if (row == 1)
				{
					row = 0;
				}
				else
				{
					row = 1;
				}
			}
			i += 1;
		}
	}
}
func main()
{
	let task: Triangle = Triangle();
	/*
	                               1
	                            1     1
	                         1     3     1
	                      1     5     5     1
	                   1     7     13    7     1
	                1     9     25    25    9     1
	             1     11    41    63    41    11    1
	          1     13     61   129   129   61    13    1
	        1    15     85   231   321   231   85    15    1
	      1    17   113   377    681   681  377   113   17   1
	    ----------------------------------------------------------
	*/
	task.tribonacciTriangle(10);
}
main();

Output

  1
  1  1
  1  3  1
  1  5  5  1
  1  7  13  7  1
  1  9  25  25  9  1
  1  11  41  63  41  11  1
  1  13  61  129  129  61  13  1
  1  15  85  231  321  231  85  15  1
  1  17  113  377  681  681  377  113  17  1
// Kotlin program for
// Tribonacci triangle
class Triangle
{
	fun tribonacciTriangle(n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows and n+1 columns
		val dp: Array < Array < Int >> = Array(2)
		{
			Array(n + 1)
			{
				0
			}
		};
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select first row which position is 0
		var row: Int = 0;
		// Auxiliary variables
		var temp: Int;
		var back: Int = 0;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						temp = dp[row][j];
						// Change second row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
						back = temp;
					}
					else
					{
						temp = dp[row][j];
						// Change first row 'j' column value
						// Combination of three elements
						dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
						back = temp;
					}
				}
				print(" " + dp[row][j]);
				j += 1;
			}
			back = 1;
			print("\n");
			if (i > 1)
			{
				if (row == 1)
				{
					row = 0;
				}
				else
				{
					row = 1;
				}
			}
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Triangle = Triangle();
	/*
	                               1
	                            1     1
	                         1     3     1
	                      1     5     5     1
	                   1     7     13    7     1
	                1     9     25    25    9     1
	             1     11    41    63    41    11    1
	          1     13     61   129   129   61    13    1
	        1    15     85   231   321   231   85    15    1
	      1    17   113   377    681   681  377   113   17   1
	    ----------------------------------------------------------
	*/
	task.tribonacciTriangle(10);
}

Output

 1
 1 1
 1 3 1
 1 5 5 1
 1 7 13 7 1
 1 9 25 25 9 1
 1 11 41 63 41 11 1
 1 13 61 129 129 61 13 1
 1 15 85 231 321 231 85 15 1
 1 17 113 377 681 681 377 113 17 1

Time Complexity

The time complexity of this algorithm is O(n^2), where 'n' is the number of rows in the Tribonacci triangle. This is because we have nested loops that iterate through each row and column of the triangle. The outer loop runs 'n' times, and the inner loop runs from 0 to 'n', resulting in a quadratic time complexity.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment