118. 杨辉三角

题目链接（简单）

题目描述

给定一个非负整数 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]]

核心思路

杨辉三角的规律：

1. 每行第一个和最后一个元素都是 1；
2. 中间的元素等于上一行同列和上一行前一列之和：

$$\text{row}[i][j] = \text{row}[i-1][j-1] + \text{row}[i-1][j]$$

因此可以从第一行 [1] 开始，逐行递推生成。

方法：逐行递推

思路及解法

1. 初始化结果 res = []；
2. 对每一行 i（从 0 到 numRows - 1）：
   • 创建长度为 i + 1 的行 row，全部填 1；
   • 对中间位置 j（从 1 到 i - 1）：
     • row[j] = res[i-1][j-1] + res[i-1][j]；
   • 把 row 加入 res；
3. 返回 res。

为什么全部填 1 再改中间：每行首尾固定为 1，直接初始化为 1，只需要更新中间的元素，代码最简洁。

举例：numRows = 5

第 0 行：[1]
第 1 行：[1, 1]
第 2 行：[1, 1+1=2, 1] = [1, 2, 1]
第 3 行：[1, 1+2=3, 2+1=3, 1] = [1, 3, 3, 1]
第 4 行：[1, 1+3=4, 3+3=6, 3+1=4, 1] = [1, 4, 6, 4, 1]

代码

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        res = []

        for i in range(numRows):
            row = [1] * (i + 1)          # 首尾都是 1

            for j in range(1, i):
                row[j] = res[i - 1][j - 1] + res[i - 1][j]

            res.append(row)

        return res

复杂度分析

• 时间复杂度：$O(\text{numRows}^2)$，第 i 行有 i + 1 个元素，共需计算 $\sum_{i=0}^{n-1} (i+1) = \frac{n(n+1)}{2}$ 个元素。
• 空间复杂度：$O(\text{numRows}^2)$，结果数组共存储 $\frac{n(n+1)}{2}$ 个数。

---

另一种写法：只依赖上一行

思路及解法

用一个变量 prev 保存上一行，逐行生成新行：

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        res = []
        prev = []

        for i in range(numRows):
            row = [1] * (i + 1)
            for j in range(1, i):
                row[j] = prev[j - 1] + prev[j]
            res.append(row)
            prev = row

        return res

两种写法本质相同，第一种直接通过 res[i-1] 访问上一行，更简洁；第二种用 prev 变量，更直观地表达「只依赖上一行」。

复杂度分析

• 时间复杂度：$O(\text{numRows}^2)$。
• 空间复杂度：$O(\text{numRows}^2)$，结果数组。

---

关键细节

1. 为什么每行首尾都是 1

杨辉三角的定义：每行的第一个和最后一个元素都是 1。所以初始化 [1] * (i + 1) 后，只需要更新中间部分。

2. 中间元素的索引范围

j 从 1 到 i - 1：

• j = 0 和 j = i 是首尾，保持为 1；
• j 从 1 到 i - 1 才是需要递推的中间元素。

注意：range(1, i) 恰好覆盖 1 到 i-1，对于 i = 0 或 i = 1，range(1, i) 为空，不会执行内层循环，直接得到 [1] 或 [1, 1]。

3. 与组合数的关系

杨辉三角第 k 行第 c 列 = $\binom{k}{c}$。也可以用组合数公式直接生成，但需要额外的阶乘或递推，反而更麻烦。逐行递推是本题最直观、最高效的做法。

4. 边界情况

• numRows = 1：返回 [[1]]；
• numRows = 0：题目保证 >= 1，但代码也能处理（循环不执行，返回 []）。

5. 空间能否优化

如果只需要第 k 行（如 LC 119），可以用两个变量滚动，空间 $O(k)$。但本题要求返回所有行，结果本身就需要 $O(n^2)$ 空间，无法优化。

---

总结

• 核心规律：每行首尾为 1，中间元素 = 上一行同列 + 上一行前一列；
• 递推公式：row[j] = prev[j-1] + prev[j]；
• 实现方式：逐行生成，每行初始化为 [1] * (i+1)，只更新中间；
• 时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$；
• 通用套路：「杨辉三角」→ 逐行递推，只依赖上一行。

相关题目

• LC 119. 杨辉三角 II（只返回第 k 行，可优化到 $O(k)$ 空间）
• LC 62. 不同路径（组合数应用）