Building Pascal's triangle row by row

Print the first n rows of Pascal's triangle. Row 1 is 1. Every other row starts and ends with 1, and each number in between is the sum of the two directly above it.

Worked example#

For n = 5:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

The 6 in the last row is 3 + 3 from the row above. The 4s are 1 + 3 and 3 + 1.

The idea#

Each row is built from the one before it, and only the one before it. So keep the last row, build the next from it, and repeat.

next = [1]
for i in 0 .. len(row) - 2:
    next.append(row[i] + row[i + 1])
next.append(1)

The loop stops one short of the end, because each new middle value needs a pair, and the last element has nothing after it to pair with. The two 1s at the ends are added separately: they are the positions where there is only one number above, not two.

What this actually is#

Each entry is a binomial coefficient: row r, position c is the number of ways to choose c things from r. You could compute each one with factorials and get the same triangle.

Building it row by row instead is quietly the first dynamic programming you will write. Each value is worked out once from values already known, and reused by the two entries below it. No recursion, no memo table, just filling in a row at a time.

That is worth noticing now, because when dynamic programming arrives properly it will look like this: a table, filled in an order that makes everything ready when you need it.

Constraints#

• 1 <= n <= 30