Pascal’s Triangle using Dynamic Programming

If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So using dynamic programming we can create a 2D array that stores previously generated values. In order to generate a value in a line, we can use the previously stored values from array.

Cases:

If line == 0 or line == i

arr[line][i] =1

Else:

arr[line][i] = arr[line-1][i-1] + arr[line-1][i]

Below is the implementation of the above approach:

C++

// C++ program for Pascal’s Triangle
// A O(n^2) time and O(n^2) extra space 
// method for Pascal's Triangle
#include <bits/stdc++.h>
using namespace std;
 
void printPascal(int n)
{
     
    // An auxiliary array to store 
    // generated pascal triangle values
    int arr[n][n]; 
 
    // Iterate through every line and 
    // print integer(s) in it
    for (int line = 0; line < n; line++)
    {
        // Every line has number of integers 
        // equal to line number
        for (int i = 0; i <= line; i++)
        {
        // First and last values in every row are 1
        if (line == i || i == 0)
            arr[line][i] = 1;
           
        // Other values are sum of values just 
        // above and left of above
        else
            arr[line][i] = arr[line - 1][i - 1] + 
                            arr[line - 1][i];
        cout << arr[line][i] << " ";
        }
        cout << "\n";
    }
}
 
// Driver code
int main()
{
    int n = 5;
    printPascal(n);
    return 0;
}
 
// This code is Contributed by Code_Mech.

C

// C program for Pascal’s Triangle
// A O(n^2) time and O(n^2) extra space 
// method for Pascal's Triangle
void printPascal(int n)
{
// An auxiliary array to store 
// generated pascal triangle values
int arr[n][n]; 
 
// Iterate through every line and print integer(s) in it
for (int line = 0; line < n; line++)
{
    // Every line has number of integers 
    // equal to line number
    for (int i = 0; i <= line; i++)
    {
    // First and last values in every row are 1
    if (line == i || i == 0)
        arr[line][i] = 1;
    // Other values are sum of values just 
    // above and left of above
    else
        arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
    printf("%d ", arr[line][i]);
    }
    printf("\n");
}
}
// Driver code
int main()
{
int n = 5;
    printPascal(n);
    return 0;
}

Java

// java program for Pascal's Triangle
// A O(n^2) time and O(n^2) extra 
// space method for Pascal's Triangle
import java.io.*;
 
class GFG {
    public static void main (String[] args) {
        int n = 5;
        printPascal(n);
    }
 
public static void printPascal(int n)
{
// An auxiliary array to store generated pascal triangle values
int[][] arr = new int[n][n]; 
 
// Iterate through every line and print integer(s) in it
for (int line = 0; line < n; line++)
{
    // Every line has number of integers equal to line number
    for (int i = 0; i <= line; i++)
    {
    // First and last values in every row are 1
    if (line == i || i == 0)
        arr[line][i] = 1;
    else // Other values are sum of values just above and left of above
        arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
    System.out.print(arr[line][i]);
    }
    System.out.println("");
}
}
}

Python3

# Python3 program for Pascal's Triangle
 
# A O(n^2) time and O(n^2) extra 
# space method for Pascal's Triangle
def printPascal(n:int):
 
    # An auxiliary array to store 
    # generated pascal triangle values
    arr = [[0 for x in range(n)] 
              for y in range(n)] 
 
    # Iterate through every line
    # and print integer(s) in it
    for line in range (0, n):
 
        # Every line has number of 
        # integers equal to line number
        for i in range (0, line + 1):
 
            # First and last values 
            # in every row are 1
            if(i is 0 or i is line):
                arr[line][i] = 1
                print(arr[line][i], end = " ") 
 
            # Other values are sum of values
            # just above and left of above 
            else:
                arr[line][i] = (arr[line - 1][i - 1] +
                                arr[line - 1][i])
                print(arr[line][i], end = " ")             
        print("\n", end = "")
 
# Driver Code
n = 5
printPascal(n)
 
# This code is contributed 
# by Sanju Maderna

C#

// C# program for Pascal's Triangle
// A O(n^2) time and O(n^2) extra 
// space method for Pascal's Triangle
using System;
 
class GFG 
{
public static void printPascal(int n)
{
     
// An auxiliary array to store 
// generated pascal triangle values
int[,] arr = new int[n, n]; 
 
// Iterate through every line
// and print integer(s) in it
for (int line = 0; line < n; line++)
{
    // Every line has number of 
    // integers equal to line number
    for (int i = 0; i <= line; i++)
    {
         
    // First and last values 
    // in every row are 1
    if (line == i || i == 0)
        arr[line, i] = 1;
    else // Other values are sum of values
         // just above and left of above
        arr[line, i] = arr[line - 1, i - 1] + 
                       arr[line - 1, i];
    Console.Write(arr[line, i]);
    }
Console.WriteLine("");
}
}
 
// Driver Code
public static void Main () 
{
    int n = 5;
    printPascal(n);
}
}
 
// This code is contributed 
// by Akanksha Rai(Abby_akku)

Javascript

<script>
 
// javascript program for Pascal's Triangle
// A O(n^2) time and O(n^2) extra 
// space method for Pascal's Triangle
var n = 5;
printPascal(n);
 
function printPascal(n)
{
// An auxiliary array to store generated pascal triangle values
arr = a = Array(n).fill(0).map(x => Array(n).fill(0));
 
// Iterate through every line and print integer(s) in it
for (line = 0; line < n; line++)
{
    // Every line has number of integers equal to line number
    for (i = 0; i <= line; i++)
    {
    // First and last values in every row are 1
    if (line == i || i == 0)
        arr[line][i] = 1;
    else
    // Other values are sum of values just above and left of above
        arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
    document.write(arr[line][i]);
    }
    document.write("<br>");
}
}
 
// This code is contributed by 29AjayKumar 
 
</script>

PHP

<?php
// PHP program for Pascal’s Triangle
// A O(n^2) time and O(n^2) extra space 
// method for Pascal's Triangle
function printPascal($n)
{
    // An auxiliary array to store 
    // generated pascal triangle values
    $arr = array(array()); 
     
    // Iterate through every line and 
    // print integer(s) in it
    for ($line = 0; $line < $n; $line++)
    {
        // Every line has number of integers 
        // equal to line number
        for ($i = 0; $i <= $line; $i++)
        {
            // First and last values in every row are 1
            if ($line == $i || $i == 0)
                $arr[$line][$i] = 1;
                 
            // Other values are sum of values just 
            // above and left of above
            else
                $arr[$line][$i] = $arr[$line - 1][$i - 1] + 
                                $arr[$line - 1][$i];
            echo $arr[$line][$i] . " ";
        }
        echo "\n";
    }
}
 
// Driver code
$n = 5;
printPascal($n);
 
// This code is contributed
// by Akanksha Rai
?>

Output

Time Complexity: O(N^2)
Auxiliary Space: O(N^2)

Note: This method can be optimized to use O(n) extra space as we need values only from previous row. So we can create an auxiliary array of size n and overwrite values. Following is another method uses only O(1) extra space.

Pascal’s Triangle

Pascal’s triangle is a triangular array of binomial coefficients. Write a function that takes an integer value N as input and prints the first N lines of Pascal’s triangle.

Example:

The below image shows the Pascal’s Triangle for N=6

Pascal’s Triangle using Dynamic Programming

C++

C

Java

Python3

C#

Javascript

PHP

Pascal’s Triangle

Categories

Contact US

Pascal’s Triangle using Dynamic Programming

C++

C

Java

Python3

C#

Javascript

PHP

Pascal’s Triangle

Similar Reads

Categories

Contact US