#118. 杨辉三角

• LeetCode：118. 杨辉三角
• 难度：简单
• 归类：数组、动态规划
• 主解法：二维动态规划

#题目描述

给定一个整数 numRows，返回杨辉三角的前 numRows 行。

在杨辉三角中，每行的首尾元素都是 1，其余元素等于它左上方和右上方两个元素之和。

示例：

输入：numRows = 5
输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

#解题思路

杨辉三角的当前行可以由上一行推导出来，具有明确的状态依赖关系，因此可以使用动态规划逐行构造。

以第 4 行（从下标 0 开始）为例：

上一行：1  3  3  1
当前行：1  4  6  4  1
           ↖ ↗
           3 + 1 = 4

对于非首尾位置，当前元素都来自上一行相邻的两个元素。

#1. 定义 dp 数组

定义：

dp[i][j] 表示杨辉三角第 i 行、第 j 列的值

下标从 0 开始，因此：

• 第 i 行共有 i + 1 个元素；
• j 的取值范围是 [0, i]；
• 最终返回整个 dp 数组。

#2. 确定状态转移方程

每行的首尾元素固定为 1：

dp[i][0] = 1
dp[i][i] = 1

对于中间位置 0 < j < i，它由上一行的左上方和右上方元素相加得到：

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

例如：

dp[4][2] = dp[3][1] + dp[3][2]
         = 3 + 3
         = 6

#3. 初始化

第一行只有一个元素：

dp[0] = [1]

代码中也可以统一处理：创建每一行时先填充 1，这样首尾元素不需要额外赋值，只计算中间位置即可。

#4. 确定遍历顺序

由于第 i 行依赖第 i - 1 行，所以必须从上到下逐行计算。

每一行内部只有中间元素需要进行状态转移，其下标范围为：

1 <= j < i

遍历顺序如下：

第 0 行 → 第 1 行 → 第 2 行 → ... → 第 numRows - 1 行

#5. 推导过程

当 numRows = 5 时，dp 的变化如下：

#代码实现

#JavaScript

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
    const dp = [];

    for (let i = 0; i < numRows; i++) {
        // 第 i 行有 i + 1 个元素，首尾元素均为 1
        dp[i] = new Array(i + 1).fill(1);

        // 只计算当前行的中间元素
        for (let j = 1; j < i; j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }

    return dp;
};

#正确性说明

使用数学归纳法说明算法能够正确生成杨辉三角：

1. 第 0 行被初始化为 [1]，符合杨辉三角的定义。
2. 假设第 i - 1 行已经计算正确。
3. 计算第 i 行时，首尾元素被设置为 1；每个中间元素都按照 dp[i - 1][j - 1] + dp[i - 1][j] 计算，与杨辉三角的定义一致。
4. 因此第 i 行也计算正确。逐行推导后，前 numRows 行全部正确。

#复杂度分析

• 时间复杂度：O(numRows²)。一共需要生成 1 + 2 + ... + numRows 个元素。
• 空间复杂度：O(numRows²)。返回的杨辉三角本身需要占用这些空间；如果不计算返回结果所占空间，额外空间为 O(1)。

#易错点

#1. 混淆行数与数组下标

第 i 行的数组长度是 i + 1，最后一个元素的下标是 i。

#2. 中间元素的遍历范围写错

首尾元素已经是 1，中间位置应满足：

for (let j = 1; j < i; j++)

如果写成 j <= i，访问 dp[i - 1][i] 时会越界。

#3. 状态来源写反

dp[i][j] 依赖的是上一行的 j - 1 和 j：

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

不是当前行相邻元素之和。

#面试回答

可以用下面这段话快速说明思路：

定义 dp[i][j] 为杨辉三角第 i 行第 j 列的值。每行首尾元素都是 1，中间元素满足 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]。因为当前行只依赖上一行，所以从上到下逐行构造即可。时间复杂度和返回结果占用的空间复杂度都是 O(numRows²)。

#总结

本题的关键是识别出“当前行依赖上一行”的递推关系：

状态定义：dp[i][j] 表示第 i 行第 j 列的值
边界状态：dp[i][0] = dp[i][i] = 1
状态转移：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
遍历顺序：从上到下逐行计算

这是一道基础的二维动态规划题，也适合用来练习如何从题目给出的递推规律抽象出状态定义和状态转移方程。