企业官网建设流程全解析

class Solution { public: vector<vector<int>> generate(int numRows) { int i = 0, j = 0; // dp[i] 表示杨辉三角的第 i 行 vector<vector<int>> dp(numRows); for(i = 0; i < numRows; i++){ // 第 i 行有 i+1 个元素 dp[i].resize(i + 1); // 每一行的第一个和最后一个元素都是 1 dp[i][0] = dp[i][i] = 1; // 计算当前行中间的元素 for(j = 1; j < i; j++){ // 当前元素 = 上一行左上 + 上一行右上 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } } return dp; } };

你现在重点理解这三个地方就行

① 创建二维数组

vector<vector<int>> dp(numRows);

相当于先创建numRows行：

dp[0] dp[1] dp[2] dp[3] ...

但此时每一行还没有具体的元素。

② 决定每一行有几个元素

dp[i].resize(i + 1);

例如：

i = 0 → dp[0] 有 1 个 i = 1 → dp[1] 有 2 个 i = 2 → dp[2] 有 3 个 i = 3 → dp[3] 有 4 个

所以自然形成：

1 1 1 1 2 1 1 3 3 1

③ 计算中间位置

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

比如计算：

1 2 1 ↘ ↙ 3

就是：

dp[3][1] = dp[2][0] + dp[2][1];

也就是：

3 = 1 + 2

最后记住这个结构

dp[i] → 第 i 行 dp[i][j] → 第 i 行第 j 个元素 resize(i+1) → 第 i 行开 i+1 个位置 两边 → 1 中间 → 上一行左上 + 上一行右上

所以这道题实际上就是通过每一行长度逐渐增加构造出杨辉三角，再利用上一行计算当前行的中间元素。