LeetCode 118 杨辉三角 动态规划递推模型 C++二维数组题解

大家好，今日打卡分享经典动态规划入门题「杨辉三角」。本题是二维数组递推的标杆题，也是校招笔试、基础算法面试的高频考点，核心考察递推关系理解与二维数组操作。

题目题意

给定非负整数 numRows ，生成杨辉三角的前 numRows 行：

- 杨辉三角中，每个数等于它左上方和右上方的数之和
- 每一行的首尾元素恒为1
- 示例：输入 numRows=5 ，输出 [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

核心解题思路：递推构建

1. 初始化结构：杨辉三角第 i 行（从0开始）有 i+1 个元素，首尾元素直接初始化为1
2. 递推关系：第 i 行第 j 个元素 = 第 i-1 行第 j-1 个元素 + 第 i-1 行第 j 个元素
3. 按行构建：从第2行开始，逐行根据上一行的值计算当前行的中间元素，全程时间复杂度O(n²)，空间复杂度O(n²)

样例原理讲解

构建第3行（索引2，元素 [1,2,1] ）：

- 首尾元素初始为1
- 中间元素 2 = 上一行（索引1）的 1 + 1 ，即 res[2][1] = res[1][0] + res[1][1]
以此类推，每一行都由上一行递推得到，逻辑完全闭环。

C++完整AC代码实现

class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res(numRows);
for(int i = 0; i < numRows; i++){
res[i].resize(i+1, 1);
for(int j = 1; j < i; j++){
res[i][j] = res[i-1][j-1] + res[i-1][j];
}
}
return res;
}
};


算法考点总结

这道题的核心是递推思想，也是二维数组、动态规划入门的基础模板题。掌握杨辉三角的构建逻辑，能帮助你快速理解「由已知推未知」的递推模型，为后续更复杂的动态规划问题打下基础。