题目要求
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。- 示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] - 示例 2:
输入: numRows = 1
输出: [[1]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pascals-triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法
数学推导，动态规划
数组的每一层都可以由上一层推导而来，简化公式为：
v [ i ] [ j + 1 ] = v [ i ? 1 ] [ j ] + v [ i ? 1 ] [ j + 1 ] ; v[i][j+1] = v[i-1][j] + v[i-1][j+1]; v[i][j+1]=v[i?1][j]+v[i?1][j+1];
其中， i i i为行数， j j j为列数。
此外，注意边界条件即可。
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<int> v0 = {1};
vector<int> v1 = {1,1};
vector<vector<int>> res;
res.push_back(v0);
if (numRows == 1)
{
return res;
}
res.push_back(v1);
if (numRows == 2)
{
return res;
}
for (int i = 2; i < numRows; i++)
{
vector<int> v(i+1,1);
for (int j = 0; j < i; j++)
{
if (j + 1 < i)
{
v[j+1] = res[i-1][j] + res[i-1][j+1];
}
}
res.push_back(v);
}
return res;
}
};
复杂度分析
时间复杂度：
O
(
n
u
m
R
o
w
s
2
)
O(numRows^2)
O(numRows2)，基本上是数组空间大小这一数量级
空间复杂度：开辟辅助数组所出现的消耗，
O
(
n
)
O(n)
O(n)
