Questions tagged [pascals-triangle]

Pascal's triangle - is a triangular array of binomial coefficients where the elements of the first row and column are equal to one, and all other elements are the sum of the previous element in the row and column.

T[i][j] = T[i][j-1] + T[i-1][j];

Example:

 1  1  1  1  1  1  1  1  1 
 1  2  3  4  5  6  7  8 
 1  3  6 10 15 21 28 
 1  4 10 20 35 56 
 1  5 15 35 70 
 1  6 21 56 
 1  7 28 
 1  8 
 1 

Iterative method of filling an array:

int n = 9;
// an array of 'n' rows
int[][] arr = new int[n][];
// iterate over the rows of the array
for (int i = 0; i < n; i++) {
    // a row of 'n-i' elements
    arr[i] = new int[n - i];
    // iterate over the elements of the row
    for (int j = 0; j < n - i; j++) {
        if (i == 0 || j == 0) {
            // elements of the first row
            // and column are equal to one
            arr[i][j] = 1;
        } else {
            // all other elements are the sum of the
            // previous element in the row and column
            arr[i][j] = arr[i][j - 1] + arr[i - 1][j];
        }
    }
}