Arrays - Building Java Programs: A Back to Basics Approach - page 475

We just need to flesh out the details of how a new row is constructed. This is a
jagged array because each row has a different number of elements. Looking at the tri-
angle, you'll see that the first row (row 0) has one value in it, the second row (row 1)
has two values in it, and so on. In general, row i has (i + 1) values, so we can
refine our pseudocode as follows:

for (int i = 0; i < triangle.length; i++) {
triangle[i] = new int[i + 1];
fill in triangle[i] using triangle[i - 1].

}

We know that the first and last values in each row should be 1 :

for (int i = 0; i < triangle.length; i++) {
triangle[i] = new int[i + 1];
triangle[i][0] = 1;
triangle[i][i] = 1;
fill in the middle of triangle[i] using triangle[i - 1].

}

And we know that the middle values come from the previous row. To figure
out how to compute them, let's draw a picture of the array we are attempting to
build:

[0] [1] [2] [3] [4] [5]

[0]

1

triangle [1]

1 1

[2] 1 2 1

[3] 1 3 3 1

[4] 1 4 6 4 1

[5] 1 5 10 10 5 1

We have already written code to fill in the 1 that appears at the beginning and end
of each row. We now need to write code to fill in the middle values. Look at row 5 for
an example. The value 5 in column 1 comes from the sum of the values 1 in column
0 and 4 in column 1 in the previous row. The value 10 in column 2 comes from the
sum of the values in columns 1 and 2 in the previous row.
More generally, each of these middle values is the sum of the two values from
the previous row that appear just above and to the left of it. In other words, for column
j the values are computed as follows:

triangle[i][j] = (value above and left) + (value above).