如何有效地计算帕斯卡三角形中的一行？

Question

我对找到帕斯卡三角形的第n行（不是特定元素而是整个行本身）感兴趣。什么是最有效的方法？

我考虑了通过汇总上面一行中的相应元素来构造三角形的常规方法：

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

另一种方法是使用特定元素的组合公式：

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

对于该行中的每个元素，我估计前一种方法将花费更多时间，具体取决于计算组合的方式。有任何想法吗？

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]

这使用以下身份：

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

因此，您可以C(n,0) = 1从此开始，然后使用此标识来计算该行的其余部分，每次将前一个元素乘以(n-k) / (k+1)。