1.题目链接：

118. 杨辉三角 - 力扣（LeetCode）

2.题目描述：

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

3.解题思路：

这段代码采用了动态规划的思路，通过构建二维数组来生成杨辉三角。首先，创建一个大小为 numRows 的二维数组 res，用来存储每一行的数字。在每一行的开始，调整每一行的大小为 i+1（其中 i 是行号），并将每一行的第一个和最后一个元素设置为 1，这是杨辉三角的边界条件。接着，从第三行开始，通过嵌套的循环填充每行的内部元素。每个内部元素的值等于上一行相邻两个元素之和，即 res[i][j] = res[i-1][j-1] + res[i-1][j]。这种方式逐步计算出每行的所有元素，最终生成完整的杨辉三角，并返回整个数组。

数学原理：组合恒等式 C(n,k)=C(n−1,k−1)+C(n−1,k)

4.题解代码：

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> res(numRows);// 创建一个二维 vector，大小为 numRows，表示杨辉三角的行数for (int i = 0; i < res.size(); i++) // 遍历每一行{res[i].resize(i + 1, 0);// 调整每一行的大小为 i+1，并初始化所有元素为 0vres[i][0] = res[i][i] = 1;// 将每一行的第一个元素和最后一个元素设置为 1// 这是杨辉三角的边界条件：每行的第一个和最后一个数都是 1}for (int i = 2; i < res.size(); i++) //从第三行开始填充杨辉三角的内部元素{// 填充每行的内部元素，由上面两行的相邻元素相加得到for (int j = 1; j < i; j++){res[i][j] = res[i - 1][j - 1] + res[i - 1][j];// 当前元素等于上一行的相邻两个元素之和}}return res;}
};

5.示例演算：

当numrows = 4时

步骤	操作	结果
初始化	创建4行空vector	[ ], [ ], [ ], [ ]
边界设置	设置首尾为1	[1], [1,1], [1, ,1], [1, , ,1]
计算第2行	res[2][1]=res[1][0]+res[1][1]	[1], [1,1], [1,2,1], [1, , ,1]
计算第3行	res[3][1]=res[2][0]+res[2][1] res[3][2]=res[2][1]+res[2][2]	[1], [1,1], [1,2,1], [1,3,3,1]

6.复杂度计算：

时间复杂度：其中n为行数。需填充n(n+1)/2​个元素，故时间复杂度为O(n^2)

空间复杂度：用了一个二维 vector 数组 res 来存储整个杨辉三角,故空间复杂度为O(n^2)

7.拓展：

递归解法：

class Solution {
public:vector<vector<int>> generate(int numRows) {if (numRows == 1) return {{1}};vector<vector<int>> prev = generate(numRows - 1);vector<int> newRow(numRows, 1);for (int j = 1; j < numRows - 1; j++) {newRow[j] = prev.back()[j - 1] + prev.back()[j];}prev.push_back(newRow);return prev;}
};

 时间复杂度：O(n^2)

 空间复杂度：O(n^2)

数学解法：

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> res;for (int i = 0; i < numRows; i++) {vector<int> row;for (int j = 0; j <= i; j++) {row.push_back(combination(i, j)); // 计算组合数C(i,j)}res.push_back(row);}return res;}private:int combination(int n, int k) {long res = 1; // 避免乘法溢出for (int i = 1; i <= k; i++) {res = res * (n - i + 1) / i; // 递推公式}return (int)res;}
};

 时间复杂度：O(n^3)

 空间复杂度：O(n^2)