难度: Easy
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1 输出: [[1]]
提示:
1 <= numRows <= 30
Submission
运行时间: 15 ms
内存: 15.9 MB
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = [[1]]
if numRows == 1:
return ans
for i in range(2, numRows+1):
row = []
for j in range(i):
if j == 0 or j == i - 1:
row.append(1)
else:
row.append(ans[i-2][j-1] + ans[i-2][j])
ans.append(row)
return ans
Explain
这个题解采用了动态规划的思路。从第二行开始，每一行的数字都等于上一行相邻两个数字之和。具体来说，从第二行开始，每行的第一个和最后一个数字都是1，中间的每个数字等于上一行它左右两个数字之和。在编码实现时，用一个二维列表 ans 来保存结果，其中 ans[i] 表示第 i 行的数字。从第二行开始，每次遍历当前行的每个位置，如果是第一个或最后一个位置，直接添加1；如果是中间位置，将上一行左右两个位置的数字相加得到当前位置的数字。
时间复杂度: O(numRows^2)
空间复杂度: O(numRows^2)
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = [[1]] # 初始化结果列表，第一行为 [1]
if numRows == 1:
return ans # 如果只有一行，直接返回结果
for i in range(2, numRows+1): # 从第二行开始遍历
row = [] # 当前行的数字
for j in range(i): # 遍历当前行的每个位置
if j == 0 or j == i - 1: # 如果是第一个或最后一个位置
row.append(1) # 直接添加 1
else: # 如果是中间位置
row.append(ans[i-2][j-1] + ans[i-2][j]) # 将上一行左右两个位置的数字相加
ans.append(row) # 将当前行添加到结果列表中
return ans # 返回结果列表
Explore
杨辉三角中，每行的第一个和最后一个数字代表的是组合数学中的组合系数，具体是从n个不同元素中选取0个元素和n个元素的组合方式，这两种情况都只有一种方法，因此这两个位置的数字总是1。
在题解中实现的动态规划方法中不会出现数组访问越界的问题。这是因为代码中已经明确了访问的边界，即只有当索引j在1到i-2之间（即非首尾）时，才会尝试访问上一行的元素。首尾元素直接赋值为1，因此不存在访问上一行不存在的元素的情况。
题解中确实考虑了numRows为1的情况。在代码开始部分，如果numRows的值为1，就直接返回初始化时包含单个元素[1]的列表。这样处理确保了当只需要一行时，程序能够正确返回结果，不会进入后续的行遍历逻辑。