118. 杨辉三角

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

二、解题思路

• 每一行的第一个和最后一个元素是 1；

• 中间的元素 = 上一行左上角 + 右上角的两个数字之和。

三、代码

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> triangle;for (int i = 0; i < numRows; ++i) {vector<int> row(i + 1, 1); // 每行先填充 1// 从第 2 行开始计算中间的数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²)，因为每一行最多要填 numRows 个数；

• 空间复杂度：O(numRows²)，存储所有值。