algorithm - How to efficiently calculate a row in pascal's triangle?

Question

I'm interested in finding the nth row of pascal triangle (not a specific element but the whole row itself). What would be the most efficient way to do it?

I thought about the conventional way to construct the triangle by summing up the corresponding elements in the row above which would take:

1 + 2 + .. + n = O(n^2)

Another way could be using the combination formula of a specific element:

c(n, k) = n! / (k!(n-k)!)

for each element in the row which I guess would take more time the the former method depending on the way to calculate the combination. Any ideas?

Answer 1

>>> def pascal(n):
...   line = [1]
...   for k in range(n):
...     line.append(line[k] * (n-k) / (k+1))
...   return line
... 
>>> pascal(9)
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

This uses the following identity:

C(n,k+1) = C(n,k) * (n-k) / (k+1)

So you can start with C(n,0) = 1 and then calculate the rest of the line using this identity, each time multiplying the previous element by (n-k) / (k+1).