[118] 杨辉三角 (Pascal's Triangle)

难度：简单 | 标签：数组、动态规划

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1：

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

解法：数学模拟 (Mathematical Simulation) —— 推荐 ✅

利用杨辉三角的性质直接构造：

1. 第 i 行有 i+1 个元素。
2. 每行的第一个和最后一个元素都是 1。
3. 中间的元素满足公式：val[i][j] = val[i-1][j-1] + val[i-1][j]。

代码实现 (C++)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        for(int i = 0; i < numRows; i++) {
            // 1. 初始化当前行：
            // 创建一个长度为 i+1 的数组，并将所有元素初始化为 1。
            // 这样 res[i][0] 和 res[i][i] 就自动是 1 了，不用额外处理。
            res.push_back(vector<int>(i + 1, 1));
            
            // 2. 计算中间的元素 (从第 2 个到倒数第 2 个)
            for(int j = 1; j < i; j++) {
                // 左上方 + 右上方
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：。需要计算总共 个数字。

• 空间复杂度：。不考虑存储返回结果所需的空间。

易错点分析

1. 内存分配： 必须使用 res.push_back(...) 或者 res.resize(...) 先分配行的空间，不能直接用 res[i] 赋值，否则会报错。
2. 下标边界： 内层循环 j 必须从 1 开始，到 i-1 结束。因为第 0 个和第 i 个元素已经在初始化时被设为 1 了，不需要计算。