7.1 KiB
tags, create time
| tags | create time | ||||
|---|---|---|---|---|---|
|
2026-05-16 18:45 |
82. 杨辉三角（Pascal's Triangle）
[!quote] LeetCode 原题 · 简单 给定一个非负整数
numRows，生成「杨辉三角」的前numRows行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
- 输入范围：
1 <= numRows <= 30
题面
示例 1：
输入：numRows = 5
输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2：
输入：numRows = 1
输出：[[1]]
思路
第一步：观察规律
拿出一张纸来，随手写几行看看——
第 0 行: 1
第 1 行: 1 1
第 2 行: 1 2 1
第 3 行: 1 3 3 1
第 4 行: 1 4 6 4 1
[!question] 💡 思考 仔细观察每一行的首尾元素和中间元素，你能发现什么共同特征？
有两个关键观察：
- 每行的第一个和最后一个元素都是 1 ——这是边界条件，不需要计算。
- 中间每个元素 = 左上方 + 右上方 ——这就是题目描述的递推关系。
具体来说，如果用 triangle[i][j] 表示第 i 行第 j 列的元素（从 0 开始），那么：
triangle[i][0] = triangle[i][i] = 1（边界）triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]（中间元素）
第二步：理解"左上方和右上方"
用 Mermaid 来看看依赖关系——
flowchart LR
subgraph "构建第 2 行 [1, 2, 1]"
A["triangle[2][0]=1\n(固定为1)"] --> C["triangle[2][1]\n= ?"]
B["triangle[2][2]=1\n(固定为1)"] -.->|不参与| C
C --> D["triangle[2][1]=1+1=2"]
end
subgraph "值从哪里来?"
E["triangle[1][0]=1"] -->|"左上方"| C
F["triangle[1][1]=1"] -->|"右上方"| C
end
style A fill:#dbeafe,stroke:#2563eb
style B fill:#dbeafe,stroke:#2563eb
style D fill:#fef3c7,stroke:#f59e0b
style C fill:#fef3c7,stroke:#f59e0b
换句话说——对于 triangle[i][j]（既不是第一个也不是最后一个）：
- 左上方 → 上一行、前一列 →
triangle[i-1][j-1] - 右上方 → 上一行、同一列 →
triangle[i-1][j]
为什么不会越界？因为第 i 行有 i+1 个元素（下标 0..i），而上一行有 i 个元素（下标 0..i-1）。当你在第 i 行的中间位置取时，j-1 最小是 0（不会小于 0），j 最大是 i-1（不会超出上一行的范围）。
第三步：自底向上逐行构造
以 numRows = 5 为例，逐步填充：
| 步骤 | 当前行 | 操作 | 结果 |
|---|---|---|---|
| 1 | 第 0 行 | 只有一个元素，直接放 1 | [1] |
| 2 | 第 1 行 | 首尾为 1，无中间元素 | [1, 1] |
| 3 | 第 2 行 | 首尾为 1，中间 = 1+1 |
[1, 2, 1] |
| 4 | 第 3 行 | 首尾为 1，中间 = 1+2, 2+1 |
[1, 3, 3, 1] |
| 5 | 第 4 行 | 首尾为 1，中间 = 1+3, 3+3, 3+1 |
[1, 4, 6, 4, 1] |
flowchart TD
subgraph "逐行构造过程"
R0["第 0 行: [1]"] --> R1["第 1 行: [1, 1]"]
R1 --> R2["第 2 行: 首尾填 1<br/>中间 = 1+1=2"]
R2 --> R3["第 3 行: 首尾填 1<br/>中间 = 1+2=3, 2+1=3"]
R3 --> R4["第 4 行: 首尾填 1<br/>中间 = 1+3=4, 3+3=6, 3+1=4"]
end
style R0 fill:#dbeafe,stroke:#2563eb
style R4 fill:#dcfce7,stroke:#16a34a
代码提示
在动手写代码之前，想一想这些关键决策点：
[!question] 💡 思考 1 Go 语言中如何声明"二维切片"（切片切片
[][]int）？需要先预分配外层长度，内层逐个分配吗？
答案是：外层可以用 make([][]int, numRows) 一次性创建；然后对每一行分别用 make([]int, i+1) 创建，最后再填充数值。两步完成，清晰且高效。
[!question] 💡 思考 2 循环怎么写最简洁？需要区分"第一行"这种特殊case 吗？
不需要！只要先统一把每行的首尾赋值为 1，再只遍历中间元素做加法就行——边界条件天然处理了，无需分支判断。
技巧
利用对称性减少计算量
杨辉三角的每一行都是回文的。比如第 4 行 [1, 4, 6, 4, 1]，左右完全对称。这意味着：
- 计算一半就够了，另一半直接镜像过去
- 对于较大的
numRows，能减少约一半的计算
不过 numRows ≤ 30 的情况下，优化意义不大，完整写出更直观。
杨辉三角 ↔ 二项式系数
杨辉三角的第 i 行第 j 列恰好等于组合数 $C(i, j)$：
\text{triangle}[i][j] = C(i, j) = \frac{i!}{j!(i-j)!}
所以这也是一道数学题。直接用组合数公式可以一行一行算，但需要注意阶乘溢出问题（Go 中 int 到 30 行没问题，更大就需要 math/big 了）。
| 方法 | 时间 | 空间 | 评价 |
|---|---|---|---|
| 模拟递推（推荐） | O(numRows²) | O(numRows²) | 最简单直观，不需要额外知识 |
| 组合数公式 | O(numRows²) | O(numRows²) | 需要考虑溢出 |
| 单行滚动数组 | O(numRows²) | O(numRows) | 只需保存一行，但代码反而复杂 |
代码
Go 语言实现
// generate generates the first numRows rows of Pascal's triangle.
// Each element is the sum of the two elements directly above it.
func generate(numRows int) [][]int {
// 初始化二维切片：外层长度为 numRows
triangle := make([][]int, numRows)
for i := 0; i < numRows; i++ {
// 第 i 行有 i+1 个元素
triangle[i] = make([]int, i+1)
// 1. 首尾都设为 1（边界条件）
triangle[i][0] = 1
triangle[i][i] = 1
// 2. 填充中间元素
// 注意：当 i < 2 时，没有中间元素，循环不执行
for j := 1; j < i; j++ {
triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
}
}
return triangle
}
执行过程演示（numRows = 5）
i=0: [1] ← 只有首=尾=1
i=1: [1, 1] ← 只有首=尾=1，无中间元素
i=2: [1, 1+1, 1] = [1, 2, 1] ← 中间 j=1: triangle[1][0]+triangle[1][1]
i=3: [1, 1+2, 2+1, 1] = [1, 3, 3, 1] ← 中间 j=1,2
i=4: [1, 1+3, 3+3, 3+1, 1] = [1, 4, 6, 4, 1] ← 中间 j=1,2,3
返回前 5 行 ✅
复杂度分析
- 时间复杂度：O(numRows²) — 总共需要填充
1 + 2 + 3 + ... + numRows = numRows(numRows+1)/2个元素 - 空间复杂度：O(numRows²) — 返回值本身占用的空间（不计入则额外空间为 O(1)）
举一反三
这道题是数组模拟 + 状态转移的第一道入门 DP，核心模式非常通用：
- 81-爬楼梯 — 同样是线性 DP，只不过这里的转移来自上一行的两个相邻位置
- 剑指 Offer II 098. 路径数量 — 网格中的路径计数，同样使用递推思想
- 杨辉三角 II（LeetCode 119）— 只需要第 k 行，可以用滚动数组将空间降到 O(k)
[!summary] 📌 本节要点
- 边界条件：每行的第一个和最后一个元素恒为 1
- 状态转移：triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
- 实现技巧：先建好结构，再统一填值——无需特判特殊情况