Catalan's triangle
Here given code implementation process.
// C Program for
// Catalan's triangle
#include <stdio.h>
void catalansTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
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 second row which position is 1
int row = 1;
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] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
printf(" %d", dp[row][j]);
}
// Include new line
printf("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
int main()
{
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
catalansTriangle(9);
return 0;
}Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430// Java program for
// Catalan's triangle
public class Triangle
{
public void catalansTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
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 second row which position is 1
int row = 1;
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] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
System.out.print(" " + dp[row][j]);
}
// Include new line
System.out.print("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
public static void main(String[] args)
{
Triangle task = new Triangle();
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
task.catalansTriangle(9);
}
}Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Catalan's triangle
class Triangle
{
public: void catalansTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
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 second row which position is 1
int row = 1;
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] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
cout << " " << dp[row][j];
}
// Include new line
cout << "\n";
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
};
int main()
{
Triangle *task = new Triangle();
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
task->catalansTriangle(9);
return 0;
}Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430// Include namespace system
using System;
// Csharp program for
// Catalan's triangle
public class Triangle
{
public void catalansTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
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 second row which position is 1
int row = 1;
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] = dp[row,j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row,j] = dp[0,j] + dp[row,j - 1];
}
else
{
// Change first row 'j' column value
dp[row,j] = dp[1,j] + dp[row,j - 1];
}
}
// Print element value
Console.Write(" " + dp[row,j]);
}
// Include new line
Console.Write("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
public static void Main(String[] args)
{
Triangle task = new Triangle();
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
task.catalansTriangle(9);
}
}Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430package main
import "fmt"
// Go program for
// Catalan's triangle
func catalansTriangle(n int) {
if n <= 0 {
return
}
// Optimize N *N space by using 2 rows
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 second row which position is 1
var row int = 1
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] = dp[row][j - 1]
} else if row == 1 {
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1]
} else {
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1]
}
}
// Print element value
fmt.Print(" ", dp[row][j])
}
// Include new line
fmt.Print("\n")
// Change the row
if row == 1 {
row = 0
} else {
row = 1
}
}
}
func main() {
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
catalansTriangle(9)
}Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430<?php
// Php program for
// Catalan's triangle
class Triangle
{
public function catalansTriangle($n)
{
if ($n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
$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 second row which position is 1
$row = 1;
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] = $dp[$row][$j - 1];
}
else if ($row == 1)
{
// Change second row 'j' column value
$dp[$row][$j] = $dp[0][$j] + $dp[$row][$j - 1];
}
else
{
// Change first row 'j' column value
$dp[$row][$j] = $dp[1][$j] + $dp[$row][$j - 1];
}
}
// Print element value
echo(" ".$dp[$row][$j]);
}
// Include new line
echo("\n");
// Change the row
if ($row == 1)
{
$row = 0;
}
else
{
$row = 1;
}
}
}
}
function main()
{
$task = new Triangle();
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
$task->catalansTriangle(9);
}
main();Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430// Node JS program for
// Catalan's triangle
class Triangle
{
catalansTriangle(n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
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 second row which position is 1
var row = 1;
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] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
process.stdout.write(" " + dp[row][j]);
}
// Include new line
process.stdout.write("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}
function main()
{
var task = new Triangle();
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
task.catalansTriangle(9);
}
main();Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430# Python 3 program for
# Catalan's triangle
class Triangle :
def catalansTriangle(self, n) :
if (n <= 0) :
return
# Optimize N *N space by using 2 rows
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 second row which position is 1
row = 1
i = 1
while (i <= n) :
j = 0
while (j < i) :
if (j > 0) :
if (j + 1 == i) :
# When last element
dp[row][j] = dp[row][j - 1]
elif (row == 1) :
# Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1]
else :
# Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1]
# Print element value
print(" ", dp[row][j], end = "")
j += 1
# Include new line
print(end = "\n")
# Change the row
if (row == 1) :
row = 0
else :
row = 1
i += 1
def main() :
task = Triangle()
# 1
# 1 1
# 1 2 2
# 1 3 5 5
# 1 4 9 14 14
# 1 5 14 28 42 42
# 1 6 20 48 90 132 132
# 1 7 27 75 165 297 429 429
# 1 8 35 110 275 572 1001 1430 1430
# --------------------------------------------
# Catalan's triangle when row = 9
task.catalansTriangle(9)
if __name__ == "__main__": main()Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430# Ruby program for
# Catalan's triangle
class Triangle
def catalansTriangle(n)
if (n <= 0)
return
end
# Optimize N *N space by using 2 rows
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 second row which position is 1
row = 1
i = 1
while (i <= n)
j = 0
while (j < i)
if (j > 0)
if (j + 1 == i)
# When last element
dp[row][j] = dp[row][j - 1]
elsif (row == 1)
# Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1]
else
# Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1]
end
end
# Print element value
print(" ", dp[row][j])
j += 1
end
# Include new line
print("\n")
# Change the row
if (row == 1)
row = 0
else
row = 1
end
i += 1
end
end
end
def main()
task = Triangle.new()
# 1
# 1 1
# 1 2 2
# 1 3 5 5
# 1 4 9 14 14
# 1 5 14 28 42 42
# 1 6 20 48 90 132 132
# 1 7 27 75 165 297 429 429
# 1 8 35 110 275 572 1001 1430 1430
# --------------------------------------------
# Catalan's triangle when row = 9
task.catalansTriangle(9)
end
main()Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
// Scala program for
// Catalan's triangle
class Triangle()
{
def catalansTriangle(n: Int): Unit = {
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
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 second row which position is 1
var row: Int = 1;
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) = dp(row)(j - 1);
}
else if (row == 1)
{
// Change second row 'j' column value
dp(row)(j) = dp(0)(j) + dp(row)(j - 1);
}
else
{
// Change first row 'j' column value
dp(row)(j) = dp(1)(j) + dp(row)(j - 1);
}
}
// Print element value
print(" " + dp(row)(j));
j += 1;
}
// Include new line
print("\n");
// Change the row
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 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
task.catalansTriangle(9);
}
}Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430// Swift 4 program for
// Catalan's triangle
class Triangle
{
func catalansTriangle(_ n: Int)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
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 second row which position is 1
var row: Int = 1;
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] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
print(" ", dp[row][j], terminator: "");
j += 1;
}
// Include new line
print(terminator: "\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
func main()
{
let task: Triangle = Triangle();
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
task.catalansTriangle(9);
}
main();Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430// Kotlin program for
// Catalan's triangle
class Triangle
{
fun catalansTriangle(n: Int): Unit
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
var 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 second row which position is 1
var row: Int = 1;
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] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
print(" " + dp[row][j]);
j += 1;
}
// Include new line
print("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Triangle = Triangle();
/*
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
--------------------------------------------
Catalan's triangle when row = 9
*/
task.catalansTriangle(9);
}Output
1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
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