力扣HOT100（41）动态规划-杨辉三角

一、题目核心规律（一句话讲透）

杨辉三角里，除了每行最左边和最右边的 1，中间的每个数，都等于它「左上方的数 + 正上方的数」。

对应数组下标就是：

第i行第j个数 = 第i-1行第j-1个数 + 第i-1行第j个数

举个例子：

• 第 3 行（下标 2）的中间数2= 第 2 行（下标 1）的1（j-1=0） + 第 2 行的1（j=1）
• 第 4 行（下标 3）的3= 第 3 行的1（j-1=0） + 第 3 行的2（j=1）

二、先记两个必背的基础性质（和代码直接相关）

1. 第i行（从 0 开始数）有i+1个数
   • 第 0 行（第一行）：1 个数 →[1]
   • 第 1 行（第二行）：2 个数 →[1,1]
   • 第 2 行（第三行）：3 个数 →[1,2,1]
2. 每行的第一个数和最后一个数，永远是 1
   • 不管哪一行，ret[i][0] = 1，ret[i][i] = 1

完整解题步骤

我们的目标是生成前numRows行，所以思路很直接：一行一行生成，用上一行的结果算当前行。

1. 初始化结果数组：创建一个二维数组ret，大小为numRows行
2. 遍历每一行：从第 0 行到第numRows-1行
3. 初始化当前行：
   • 给当前行分配i+1个空间（因为第 i 行有 i+1 个数）
   • 把当前行的第一个和最后一个元素设为 1
4. 计算当前行中间的数：
   • 从第 1 个位置到第i-1个位置（首尾已经是 1 了，不用算）
   • 每个位置的值 = 上一行的j-1位置 + 上一行的j位置
5. 所有行生成完毕，返回结果数组

class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> ret(numRows); for(int i=0;i<numRows;i++){ //遍历每一行. //给这个一维数组开辟出 k 个格子，准备好位置放数据。 ret[i].resize(i+1); //先把头和尾变成1 ret[i][0] = ret[i][i] = 1; //其他位置 for(int j=1;j<i;j++){ ret[i][j] = ret[i-1][j] + ret[i-1][j-1]; } } return ret; } };