0118.杨辉三角

难度：🟢 简单

标签：数组、动态规划

链接：118. 杨辉三角

题目描述

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

解题思路

核心思想

本题的核心是根据杨辉三角的生成规则，逐行构建这个二维数组。其关键规则是：

1. 每一行的第一个和最后一个元素都是 1。

2. 对于其他位置的元素 C(i, j)（第 i 行，第 j 列），它的值等于其上一行相邻两个元素之和，即 C(i-1, j-1) + C(i-1, j)。

思路选择

动态规划（或称为“模拟法”） 是解决此问题的最直观、最标准的思路。我们可以一层一层地生成杨辉三角。在生成第 i 行时，我们完全依赖于已经生成好的第 i-1 行的数据。

关键步骤

1. 处理边界情况：如果 numRows 为 0，返回一个空数组。

2. 初始化：创建一个结果数组 triangle，并首先将第一行 [1] 添加进去。

3. 循环生成：从 i = 1 开始循环到 numRows - 1，生成后续的每一行。 a. 获取上一行 prevRow = triangle[i - 1]。 b. 创建一个当前行 currentRow，并将第一个元素 1 放入。 c. 循环遍历上一行的元素，从索引 j = 1 开始，根据规则 currentRow[j] = prevRow[j - 1] + prevRow[j] 来计算当前行的中间元素。 d. 在当前行的末尾添加最后一个元素 1。 e. 将 currentRow 添加到 triangle 中。

4. 返回结果：循环结束后，返回完整的 triangle。

代码实现

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
    let results = []; // 存储杨辉三角的结果

    // 特殊情况处理
    if (numRows === 0) return results;

    // 初始化第一行
    results.push([1]);

    // 循环生成后续行
    for (let i = 1; i < numRows; i++) {
        // 先创建当前行，并用 1 填充
        let currentRow = new Array(i + 1).fill(1); 

        // 再计算并填充中间元素
        for (let j = 1; j < currentRow.length - 1; j++) {
            currentRow[j] = results[i - 1][j - 1] + results[i - 1][j];
        }

        results.push(currentRow);
    }

    return results; // 返回结果
};

复杂度分析

• 时间复杂度：O(numRows²) 我们需要一个双层循环来填充杨辉三角的每个元素。总共需要计算的元素数量级为 1 + 2 + ... + numRows，即 (numRows * (numRows + 1)) / 2，所以时间复杂度是 O(numRows²)。

• 空间复杂度：O(numRows²) 我们需要一个二维数组来存储整个杨辉三角，其空间消耗与时间复杂度同级。

相关题目

• 0119.杨辉三角 II

• 0062.不同路径

• 0070.爬楼梯

总结

本题是动态规划的入门级题目，其递推关系非常明确。通过逐行构建的方式，可以清晰地模拟出杨辉三角的生成过程，是练习二维数组操作和理解动态规划思想的好题目。