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
----------------------------------------------------------
*/
}
}``````

#### 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
----------------------------------------------------------
*/
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
----------------------------------------------------------
*/
}
}``````

#### 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
----------------------------------------------------------
*/
}
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
----------------------------------------------------------
*/
}
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() :
#                               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
#    ----------------------------------------------------------

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()
#                               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
#    ----------------------------------------------------------
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
----------------------------------------------------------
*/
}
}``````

#### 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
----------------------------------------------------------
*/
}
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
----------------------------------------------------------
*/
}``````

#### 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.

Categories
Relative Post