118. 杨辉三角 (Easy)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/pascals-triangle/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和正上方的数之和。
示例：
输入: numRows = 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
提示：
- 1 <= numRows <= 30
题目详细分析
- 数据范围：numRows <= 30，数值在 32 位整数范围内。
- 核心约束：每行长度递增 1，首尾固定为 1，中间元素由上一行计算得出。
- 边界条件：numRows = 1 时直接返回
[[1]]。 - 隐藏条件：杨辉三角第 n 行的第 k 个数等于组合数 C(n, k)，不过题目要求逐行构造而非用公式。
小白版直白理解
杨辉三角就像搭金字塔——金字塔最左边和最右边永远是 1。中间的每一块砖，都是它”左肩膀”（上一行左边）和”右肩膀”（上一行右边）两块砖的和。从塔尖的 1 开始，一层一层往下搭。
解题思路
思路一：逐行构造（推荐）
核心洞察：每行第一个和最后一个为 1，中间元素 row[j] = prev_row[j-1] + prev_row[j]。利用上一行的结果构建当前行，天然满足 DP 的状态依赖关系。
DP 五步法：
- dp 定义：无显式 dp 表，每行的 list 即为当前状态
- 初始化：每行为
[1] * (i+1) - 递推：
row[j] = res[i-1][j-1] + res[i-1][j]（j 从 1 到 i-1） - 遍历顺序：从第 0 行到第 numRows-1 行
- 举例验证：numRows=5 → 见示例
def generate(numRows):
res = [] # 存储所有行
for i in range(numRows):
row = [1] * (i + 1) # 当前行，首尾默认为 1
for j in range(1, i): # 从第 2 个到倒数第 2 个
row[j] = res[i - 1][j - 1] + res[i - 1][j]
res.append(row)
return res思路二：数学组合数法
第 n 行第 k 个数 = C(n, k)，利用组合数递推公式可求。
def generate(numRows):
res = []
for i in range(numRows):
row = [1] * (i + 1)
for j in range(1, i):
# C(i, j) = C(i, j-1) * (i - j + 1) / j
row[j] = row[j - 1] * (i - j + 1) // j
res.append(row)
return res易错点
- 行索引偏移：第 i 行有 i+1 个元素（i 从 0 开始），循环时要小心 range 的范围。
- 边界处理：
range(1, i)在 i=0 或 i=1 时自动为空，不会进入内部循环。 - 中间元素计算：依赖
res[i-1]必须在之前已构建好，顺序不可颠倒。
框架提炼
逐行构建 DP 模板：
def build_triangle(n):
res = []
for i in range(n):
row = [default] * (i + 1) # 初始化当前行
for j in range(start, end): # 填充中间元素
row[j] = f(res[i-1][j-1], res[i-1][j]) # 依赖上一行
res.append(row)
return res这种 DP 不依赖”表”而依赖”上一行结果”，适合状态只依赖前一步的滚动场景。
关联题目
- 70-爬楼梯 — 基础 DP 入门，递推思想相同
- 62-不同路径 — 路径 DP，递推关系
dp[i][j] = dp[i-1][j] + dp[i][j-1]与杨辉三角本质相同 - 120-三角形最小路径和 — 类似杨辉三角的层间递推，但求最小路径和