杨辉三角形

在数学中,杨辉三角形是一个三角形的阵列binomial coefficients.

要想画杨辉三角，先把 "1" 方在顶点，然后连续在下面按三角形的模式放上数字。

每个数是它上面两个数的和。

公式

n 是 排 , k是 行内的第几个

进入nth排和kth列的杨辉三角形表示. 例如,最上面一行中的唯一非零条目是.

使用这种表示法,前一段的结构可写如下:

对于任何非负整数n和任何在0和n之间的整数k, 概括.

在O (n) 时间内计算三角形条目

我们知道

第i个-和第lineNumber行 组合为 C(lineNumber, i)二项式系数 并且所有行都以1值开头.

想法是计算C(lineNumber, i)通过C(lineNumber, i-1). 下面内容,只需要 O(1)时间:

C(lineNumber, i)   = lineNumber! / ((lineNumber - i)! * i!)
C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!)

我们可以从以上两个表达式中得出以下表达式:

C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i

所以C(lineNumber, i)算出C(lineNumber, i - 1)是在O(1)时间.

参考

• Wikipedia
• GeeksForGeeks
• 数学乐