Pascal's Triangle
在 Pascal's triangle 中，第一行是 [1]。后面的每一行都比上一行多一个元素，以 1 开头和结尾，中间的每个元素都是正上方两个元素的和。你会得到一个整数 numRows。按从上到下的顺序返回三角形的前 numRows 行，每行都是一个整数数组。
函数
- numRowsinteger
- 要构建三角形的行数
- 返回值integer-2d-array
- 前 numRows 行，先显示最上面一行
约束条件
1 ≤ numRows ≤ 30- 前 30 行的每个条目都能放入 32 位有符号整数。最大值是 77558760，位于第 30 行的中间。
示例
- 输入
- numRows = 5
- 输出
- [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
- 解释
- 每个内部项都是其上方两个数相加的结果。第四行：3 = 1 + 2，3 = 2 + 1。第五行：4 = 1 + 3，6 = 3 + 3，4 = 3 + 1。
- 输入
- numRows = 1
- 输出
- [[1]]
- 解释
- 只有一行时，三角形只有顶端，即
[1]。
进阶
你能否只保留一个数组，并逐行就地更新它？内层循环必须按什么方向运行，为什么？
提示
逐个打开提示，每个都会多透露一点。
第 0 行是
[1]，第 1 行是[1, 1]。第r行有多长？它的第一个和最后一个元素是什么？每个内部条目只需要上一行中的两个值。如果你按顺序构建各行，那么需要用到上一行时，它总是已经完成了。
将每一行都初始化为全 1。然后，对于每个内部位置
c，将上一行的c-1和c位置相加。添加这一行，然后继续。
题解
每个数都是上一行中两个数的和。如果每次都从头计算每个数，就会重复计算相同的值，而且每增加一行，工作量都会翻倍。你返回的各行就是这些较小问题的已存答案，因此要从上往下构建三角形，每一行都根据上一行生成。
递归计算每个条目
结果正确，但无法在最大的测试中运行完毕
思路
行和位置都从 0 开始编号。定义可以写成一个函数：entry(row, col) 在边缘处的值为 1，也就是 col 为 0 或 row 时，其他情况下则为 entry(row-1, col-1) + entry(row-1, col)。这是正确的，因为它就是定义本身。
递归只会在边缘处停止，此时返回 1，所以一个值为 v 的项大约需要 2v 次调用。第 r 行的数值总和最多为 2^r，因此 30 行需要大约 2^31 次调用，也就是超过 20 亿次。
算法
- 编写
entry(row, col)：如果col为 0 或col等于row，则返回 1。 - 否则，返回
entry(row-1, col-1) + entry(row-1, col)。 - 对于从 0 到
numRows-1的每个row，收集从 0 到row的每个col对应的entry(row, col)。 - 返回行列表。
def pascalEntry(row, col):
if col == 0 or col == row:
return 1 # the edges of the triangle
return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)
def generate(numRows):
triangle = []
for row in range(numRows):
triangle.append([pascalEntry(row, col) for col in range(row + 1)])
return triangle根据上一行构建每一行
思路
递归会不断请求前面各行的条目，而你还是要构建这些行。因此，按从上到下的顺序计算各行；填充第 r 行时，读取已经计算完成的第 r-1 行。每个条目只需进行一次加法：较小答案组成的表格就是输出本身。
将每行初始化为 r + 1 个 1，就能设置好两侧边缘，因此第 0 行和第 1 行没有内部位置，无需特殊处理。这个三角形共有 1 + 2 + ... + n 个条目，约为 n²/2，所以时间复杂度为 O(n²)，除了输出本身，不需要额外内存：30 行有 465 个条目，而不是 20 亿次调用。
算法
- 先创建一个空的行列表。
- 对于从 0 到
numRows-1的每个row，创建row + 1个 1。 - 对于从 1 到
row-1的每个col，将其设为上一行中位置col-1和col的和。 - 添加这一行并继续。返回这个列表。
def generate(numRows):
triangle = [[1]]
for row in range(1, numRows):
above = triangle[-1]
values = [1] * (row + 1) # both edges are 1
for col in range(1, row):
values[col] = above[col - 1] + above[col]
triangle.append(values)
return triangle
易错点和边界情况
- 返回
numRows + 1行。行号从 0 开始，你需要的最后一行是numRows-1。 - 让内层循环遍历边缘位置。位置 0 没有左侧父项，位置
row没有右侧父项，因此读取它们会越界。 - 范围在行数较小时会出错。Swift 的
1..<row在row为 0 时会崩溃，而 R 的2:(row-1)在row为 2 时会倒数到 1。 - 用阶乘计算元素。
C(29, 14)可以存入 int，但29!会超出 64 位整数的范围。 - 每一行都追加同一个数组，然后再修改它。答案中的每一行都会变成最后一行。
常见问题3
生成 Pascal 三角形的时间复杂度是多少？
对于 n 行，时间复杂度为 O(n²)：三角形大约有 n²/2 个条目，每个条目都需要进行一次加法。这是最优的，因为你必须写出输出中的每个条目。除输出外，额外空间为 O(1)。
杨辉三角与二项式系数有什么关系？
第 r 行中从 0 开始计数的第 k 项是 C(r, k)，也就是从 r 个物品中选出 k 个物品的方法数。求和公式是恒等式 C(r, k) = C(r-1, k-1) + C(r-1, k)，第 r 行的总和为 2^r，也就是 r 个物品的子集数量。
你能不构建上面的行，直接计算出一行吗？
是的。从 1 开始，并从前一项得到下一项：C(r, k) = C(r, k-1) × (r-k+1) / k。先乘再除，这样除法结果是整数，并为乘积使用 64 位整数。第 r 行需要 O(r) 时间。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def generate(numRows):
# 在这里编写代码测试 #1
测试 #2
参数
numRows = 5
预期输出
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]