本篇推文共计2000个字，阅读时间约3分钟。

01

题目描述

题目描述：

给定一个非负整数numRows，

生成杨辉三角的前numRows行。

杨辉三角中，每个数是它左上方和右上方数之和。

如下面的示例：

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

提示：

1. 0 <= key <= 10^6

2. 最多调用 10^4 次 add、remove 和 contains。

02

方法和思路

从题意和杨辉三角的特性可知。

每个数是它左上方和右上方的数的和。

我们可以创建一个空数组res，

接着采用递归的方式，从第一行开始由上往下不断生成元素均为1的新数组tmp，

同时根据杨辉三角，每个数是它左上方和右上方的数的和的原理，不断更新tmp数组的值，将每一个更新数字后的数组tmp保存到空数组res中，

例如：

我输入的数字是5，则我会生成5次tmp数组的值。

第一次：tmp=[1]

此时为第一行，直接将该数组存入空数组res中。
res=[[1]]

第二次：tmp=[1,1]

此时为第二行，直接将该数组存入数组res中。
res=
[[1],
[1,1]]

第三次：tmp=[1,1,1]

此时为第三行，进行每个数是它左上方和右上方的数的和的计算。
计算完之后tmp=[1,2,1],将该数组存入数组res中。
res=
[[1],
[1,1],
[1,2,1]]

第四次：tmp=[1,1,1,1],

此时为第四行，进行每个数是它左上方和右上方的数的和的计算。
计算完之后tmp=[1,3,3,1],将该数组存入数组res中。
res=
[[1],
[1,1],
[1,2,1],
[1,3,3,1]]

第五次：tmp=[1,1,1,1,1]

此时为第四行，进行每个数是它左上方和右上方的数的和的计算。
计算完之后tmp=[1,4,6,4,1],将该数组存入数组res中。
res=
[[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]]

最后输出完全体杨辉三角res。

我们用代码表示此题的解法如下：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for i in range(numRows):
            tmp = [1] * (i + 1)
            for j in range(i + 1):
                if 0 < j < i:
                    tmp[j] = res[i - 1][j - 1] + res[i - 1][j]
            res.append(tmp)
        return res