Question

Pascal’s triangle looks as follows:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

...

The first entry in a row is 1 and the last entry is 1 (except for the first row which contains only 1), and every other entry in Pascal’s triangle is equal to the sum of the following two entries: the entry that is in the previous row and the same column, and the entry that is in the previous row and previous column.

Use dynamic programming to design an O(n²) time algorithm that computes the first n rows in Pascal’s triangle.

Answer 1

import java.util.ArrayList;

import java.util.List;

public class Main {

public static List<List<Integer>> pascalTriangle(int n) {

List<List<Integer>> triangle = new ArrayList<List<Integer>>();

if (n == 0) {

return triangle;

}

triangle.add(new ArrayList<>());

triangle.get(0).add(1);

for (int rowNum = 1; rowNum < n; rowNum++) {

List<Integer> row = new ArrayList<>();

List<Integer> prevRow = triangle.get(rowNum-1);

row.add(1);

for (int j = 1; j < rowNum; j++) {

row.add(prevRow.get(j-1) + prevRow.get(j));

}

row.add(1);

triangle.add(row);

}

return triangle;

}

public static void main(String[] args) {

int n = 10;

List<List<Integer>> triangle = pascalTriangle(n);

for (List<Integer> row : triangle) {

for (int el : row) {

System.out.print(el + " ");

}

System.out.println();

}

}

}