【C++刷题】力扣-#118-杨辉三角

题目描述

给定一个非负整数 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. 初始化：创建一个空列表 triangle 来存储杨辉三角的每一行。
2. 特殊情况：如果 numRows 为 0，返回空列表；如果 numRows 为 1，返回只有一个元素 [1] 的列表。
3. 构建杨辉三角：对于每一行 i（从 0 到 numRows - 1）：
   ○ 创建一个列表 row，初始值为 [1]，因为每一行的第一个和最后一个数字都是 1。
   ○ 如果当前行不是第一行，对于 row 中的每个位置 j（从 1 到 i - 1），计算 row[j] 的值为 triangle[i - 1][j - 1] + triangle[i - 1][j]。
   ○ 将计算好的行添加到 triangle 中。
4. 返回结果：返回 triangle。

代码实现

vector<vector<int>> generate(int numRows) {vector<vector<int>> triangle;for (int i = 0; i < numRows; i++) {std::vector<int> row(i + 1, 1); // 初始化行，首尾为1if (i > 0) {for (int j = 1; j < i; j++) {row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];}}triangle.push_back(row);}return triangle;
}

复杂度分析

● 时间复杂度：O(numRows^2)，因为我们需要计算每一行的每个数字，每个数字的计算时间是 O(1)。
● 空间复杂度：O(numRows^2)，因为我们需要存储整个杨辉三角的前 numRows 行。
这个算法的优势在于它直接模拟了杨辉三角的构建过程，不需要额外的数学计算。