杨辉三角
Pascal's Triangle
生成杨辉三角的前 numRows 行。
在力扣中练习题目描述
给定一个非负整数 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
解题思路
主解法
逐行构造 · 上一行相加
首尾为 1，中间每个数是上一行相邻两数之和
杨辉三角的每一行长度是行号 + 1，首尾固定为 1。第 i 行第 j 列（0 < j < i）等于上一行的 [j-1] 与 [j] 之和。
分步图解
先确定每一行长度；行首和行尾都是 1，内部格子才需要相加。
自拟 5 行：第 4 行的 4、6、4 分别来自 1+3、3+3、3+1。两侧的 1 不参与内部的加法，所以循环从 1 到 i-1。
图解
普通节点当前操作
每一行只依赖上一行，按行从上到下构造即可。时间 O(numRows²)，空间 O(numRows²)（输出本身占这么多）。
时间 O(numRows²)空间 O(numRows²)（含输出）
易错点
- 内部循环写成 j <= i：行尾会越界访问上一行。
- 先算 j=0：需要访问上一行的 -1 下标。
- 只保留上一行却仍返回整张表：输出本身无法压缩。
对照解法
只保留上一行
用 prev 保存上一行，逐行生成
输出仍占 O(n²)，但计算时只保留上一行，额外工作空间 O(n)；主解法直接写结果表。
如果不想依赖结果表的上一行，可以用一个 prev 向量保存上一行，生成 row 后把 prev = row。
这样当前行的计算只依赖局部变量，逻辑更独立；额外空间从“整张表”降到“上一行”，当然返回的结果仍然占 O(n²)。
它适合流式输出前 n 行、或者只需要最后一行而前面的行可以丢弃的场景。
- 1prev 初始为空。
- 2每行先填 1。
- 3用 prev 计算内部值。
- 4把 row 存入结果，prev 更新为 row。
时间 O(numRows²)空间 O(numRows²) 输出 + O(numRows) 额外
易错点
- prev 在 row 计算前就被覆盖：当前行会读到自己的值。
- 第一行 prev 为空却访问 prev[0]：需要从第二行才开始内部计算。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
numRows = 5先确定每一行长度；行首和行尾都是 1，内部格子才需要相加。
查看 C++ 代码
延伸阅读
- 杨辉三角的递推是组合数 C(i,j)=C(i-1,j-1)+C(i-1,j)，和二维 DP 的“上方 + 左上方”完全一致。
- 如果只要第 n 行，可以用一维数组倒序更新，把空间降到 O(n)。