118. 杨辉三角

Problem: 118. 杨辉三角

思路

1. 每一行首尾两个元素都是1。
2. 其余数字，等于左上方的数，加上正上方的数，即 ans[i][j]=ans[i−1][j−1]+ans[i−1][j]。

解题过程

1. 初始化二维向量 ans 。
2. 生成每一行，第 i 行有 i + 1 个元素，并且初始化为 1 。
3. 计算中间元素。

复杂度

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n^2)$

Code

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