LeetCode118 Pascal's Triangle

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given numRows, generate the first numRows of Pascal’s triangle.

样例

1
2
Input:
numRows = 5
1
2
3
4
5
6
7
8
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

思路

求$n$层的帕斯卡三角,也就是杨辉三角。

递推式如下:

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int> > ans;
for (int i = 0; i < numRows; ++i) {
vector<int> temp;
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) temp.push_back(1);
else temp.push_back(ans[i-1][j-1] +ans[i-1][j]);
}
ans.push_back(temp);
}
return ans;
}
};
分享到 评论