题目描述
思路解析
一句话答案：LeetCode 118 杨辉三角：逐行递推，每行两端为 1、中间每格等于上一行相邻两数之和。这条帕斯卡法则就是组合数 C(i,j)=C(i-1,j-1)+C(i-1,j)，省去逐格算阶乘的溢出与重复，时间 O(n²)、空间 O(n²)。
杨辉三角这道题到底要我们把什么填出来
给一个行数 numRows，摆出杨辉三角的前 numRows 行。它是个数字三角：第 0 行只有一个 1，往下每行多一个数，两端都是 1，中间每个数等于它「上一行」紧挨的两个数之和。题面给 numRows = 6，要返回前 6 行。后面说第 i 行第 j 个，行号 i、列号 j 都从 0 数起。
为什么照组合公式逐格算阶乘既慢又会溢出
杨辉三角第 i 行第 j 个数，其实就是组合数 C(i,j)（从 i 个东西里挑 j 个的取法数）。照定义每格单独算 C(i,j)=i!/(j!(i−j)!)，要反复乘阶乘（i! 就是 1×2×…×i），前面算过的又从头乘一遍。更麻烦的是阶乘涨得极快，行数稍大 i! 就冲破整数范围、乘出的大数会溢出，可那格的值明明不大，逐格硬算并不划算。
相邻两数相加背后是帕斯卡法则的组合直觉
换一个只用加法的算法，靠一条组合恒等式：C(i,j)=C(i-1,j-1)+C(i-1,j)。它说的是，从 i 个东西里挑 j 个，按「第 i 个选不选」分成两堆——不选它，从前 i-1 个里挑满 j 个，有 C(i-1,j) 种；选它，剩下的名额在前 i-1 个里挑 j-1 个，有 C(i-1,j-1) 种。两堆不重不漏加起来，正好是上一行紧挨的两个数之和，中间每格等于上方两数相加就是这么来的。
每行怎样从上一行推出，两端为何恒等于 1
有了这条法则，就能自底向上（从第 0 行起、每行只用刚填好的上一行往下推）逐行生成，不再碰阶乘。参考代码里每到第 i 行，先开一个长度 i+1 的 row、整排填 1；再让中间的 j 从 1 走到 i-1，把 row[j] 改成上一行的 res[i-1][j-1] 加 res[i-1][j]，也就是左上那个数加正上那个数。两端不进这轮修改，所以恒为 1。填完把 row 接到 res 末尾，留给下一行当依据。
拿 numRows = 6 亲手把六行填出来
第 0 行只有 1：[1]。第 1 行两端都是 1、没有中间格：[1,1]。第 2 行中间 1+1=2，得 [1,2,1]。第 3 行左边 1+2=3、右边 2+1=3，得 [1,3,3,1]。第 4 行 1+3=4、3+3=6、3+1=4，得 [1,4,6,4,1]。第 5 行 1+4=5、4+6=10、6+4=10、4+1=5，得 [1,5,10,10,5,1]。六行拼起来和题面输出逐格对上。
漏填两端的 1，最左格为什么会去够上一行不存在的邻居
三角形前 numRows 行一共约 numRows²/2 个数，每个数一次加法就填好，时间 O(n²)；这些数直接存进要返回的结果，空间也是 O(n²)。两处边界最容易出岔。第 0 行只有一格，中间那圈 j 从 1 到 i-1 不进，全靠「整排先填 1」兜住，漏了这步第一行就空着。两端的 1 同理：要是让 j 从 0 扫到 i，改最左格会取到上一行并不存在的左邻居，不是越界就是算错。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条规则，下面每一格都在套它。
空表准备好了。左边标行号，从第 0 行最左格开始往下填。
第 0 行只有一个数，它既是开头也是结尾，直接填 1。
每一行最左边一格永远是 1（左边没有邻居可加），填 1。
每一行最右边一格永远是 1（右边没有邻居可加），填 1。
每一行最左边一格永远是 1（左边没有邻居可加），填 1。
算第 2 行第 1 个：看它正上方两个数——左上 1、正上 1，把它们加起来。
1 + 1 = 2，填进第 2 行第 1 个。
每一行最右边一格永远是 1（右边没有邻居可加），填 1。
每一行最左边一格永远是 1（左边没有邻居可加），填 1。
算第 3 行第 1 个：看它正上方两个数——左上 1、正上 2，把它们加起来。
1 + 2 = 3，填进第 3 行第 1 个。
算第 3 行第 2 个：看它正上方两个数——左上 2、正上 1，把它们加起来。
2 + 1 = 3，填进第 3 行第 2 个。
每一行最右边一格永远是 1（右边没有邻居可加），填 1。
每一行最左边一格永远是 1（左边没有邻居可加），填 1。
算第 4 行第 1 个：看它正上方两个数——左上 1、正上 3，把它们加起来。
1 + 3 = 4，填进第 4 行第 1 个。
算第 4 行第 2 个：看它正上方两个数——左上 3、正上 3，把它们加起来。
3 + 3 = 6，填进第 4 行第 2 个。
算第 4 行第 3 个：看它正上方两个数——左上 3、正上 1，把它们加起来。
3 + 1 = 4，填进第 4 行第 3 个。
每一行最右边一格永远是 1（右边没有邻居可加），填 1。
每一行最左边一格永远是 1（左边没有邻居可加），填 1。
算第 5 行第 1 个：看它正上方两个数——左上 1、正上 4，把它们加起来。
1 + 4 = 5，填进第 5 行第 1 个。
算第 5 行第 2 个：看它正上方两个数——左上 4、正上 6，把它们加起来。
4 + 6 = 10，填进第 5 行第 2 个。
算第 5 行第 3 个：看它正上方两个数——左上 6、正上 4，把它们加起来。
6 + 4 = 10，填进第 5 行第 3 个。
算第 5 行第 4 个：看它正上方两个数——左上 4、正上 1，把它们加起来。
4 + 1 = 5，填进第 5 行第 4 个。
每一行最右边一格永远是 1（右边没有邻居可加），填 1。
整张杨辉三角填完了。每个内部数都是它正上方两数之和，每行两端都是 1。
边界先想清。
两个高频追问。
参考代码
def generate(numRows): res = [] for i in range(numRows): row = [1] * (i + 1) for j in range(1, i): row[j] = res[i-1][j-1] + res[i-1][j] res.append(row) return res复杂度
- 时间：O(n²)，三角共约 n²/2 个数，每个 O(1)
- 空间：O(n²)，存下整张三角（输出本身）
易错点
面试追问把动画讲成自己的话
追问只要第 k 行、不要整张三角怎么办？
追问杨辉三角和组合数有什么关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
杨辉三角 II
LeetCode 119 · 简单 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题