题目

给定一个非负整数 numRows， 生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

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

示例 2:

1
2
输入: numRows = 1
输出: [[1]]

提示:

  • 1 <= numRows <= 30

题解

同样也是十分经典的 DP 题，也是斐波那契数列，但这个是求所有的行：

双重遍历，每行的第一个数和最后一个数（i == j）都是加入 1，其他的位置就是加入上三角之和。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # 这道题目就是非常经典的斐波那契数列了
        # 先初始化最终结果数组
        res = list()
        # 遍历每行，进行每行中元素的添加
        for i in range(numRows):
            # 每行都是一个数组
            row = list()
            for j in range(0, i + 1):
                # 第一个和最后一个都是 1
                if j == 0 or j == i:
                    row.append(1)
                else:
                    # 其余位置是三角之和
                    row.append(res[i - 1][j] + res[i - 1][j - 1])
            res.append(row)

        return res

运行结果

image.png