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 ?> |
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
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