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)