给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
【示例】
输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
没什么特别的，逐行构造。
class Solution { public: vector<vector<int>> generate(int numRows) { //pT means Pascal's triangle vector<vector<int>> pT; for (int i=0; i<numRows; ++i){ vector<int> temp_vec; for (int j=0; j <= i; ++j){ if (j==i || j==0){ temp_vec.emplace_back(1); continue; } temp_vec.emplace_back(pT[i-1][j-1]+pT[i-1][j]); } pT.emplace_back(temp_vec); } return pT; } };[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
可以左对齐：
[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
从第二行开始的每一行的元素 a j a_{j} aj，都有： 1. a 0 = 1 a_{0}=1 a0=1，每一行第一个元素总是为1。 2. a j i : = a j − 1 i − 1 + a j i − 1 , r a w − 1 > i ≥ 1 a_{j}^{i}:=a_{j-1}^{i-1}+a_{j}^{i-1},raw-1> i\geq1 aji:=aj−1i−1+aji−1,raw−1>i≥1，注意这里是用上一时刻 a j a_{j} aj和当前时刻 a j − 1 a_{j-1} aj−1求和后更新 a j a_{j} aj。比如i=3时，初始数组为{1,1}，下一时刻， a 0 = 1 a_{0}=1 a0=1不变， a 1 : = a 0 + a 1 = 2 a_{1}:=a_{0}+a_{1}=2 a1:=a0+a1=2。 3. a r a w − 1 = 1 a_{raw-1}=1 araw−1=1，新增行时尾部增加1。 所以可以避免vector的重复构造，只创建一个vector即可。从第二行开始，对每一行，除第一个元素不变之外，其他元素等于上一时刻该元素值与该元素左边元素上一时刻之和，同时在尾部增加1。 实现过程中略有不同， a j a_{j} aj更新后会影响 a j + 1 a_{j+1} aj+1的计算，因此应该从右向左更新 a j a_{j} aj。此外，需要先在原vector尾部增加0。 这个思路在直接返回杨辉三角中指定行元素（杨辉三角 II）同样适用。
class Solution { public: vector<vector<int>> generate(int numRows) { //pT means Pascal's triangle vector<vector<int>> pT; if (numRows==0) return pT; vector<int> raw_vec(1,1); pT.emplace_back(raw_vec); for (int i=1; i<numRows; ++i){ raw_vec.emplace_back(0); for (int j=i; j>=1; --j){ raw_vec[j]+=raw_vec[j-1]; } pT.emplace_back(raw_vec); } return pT; } };杨辉三角每个元素实际上等于排列组合 C i j C_{i}^{j} Cij，i表示行，j表示列： C i j = i ! j ! ( i − j ) ! , i ≥ j ≥ 0 C_{i}^{j}= \frac {i!}{j!(i-j)!},i\ge j \ge0 Cij=j!(i−j)!i!,i≥j≥0 而且： C i j + 1 = C i j ∗ ( i − j ) j + 1 C_{i}^{j+1}=C_{i}^{j}*\frac{(i-j)}{j+1} Cij+1=Cij∗j+1(i−j) 也是可以递推的，这个思路也是我第一次做杨辉三角 II用的。
class Solution { public: vector<vector<int>> generate(int numRows) { //pT means Pascal's triangle vector<vector<int>> pT; for (int i=0; i<numRows; ++i){ vector<int> temp_vec(1,1); for (int j=1; j<=i; ++j){ temp_vec.emplace_back(temp_vec[j-1]*(i-(j-1))/j); } pT.emplace_back(temp_vec); } return pT; } };本质和迭代构造相同，下面有两种写法，第一种看上去简洁，但是涉及到大量的拷贝构造，所以耗时不小；第二种方式新构造了一个迭代函数，且使用引用参数，避免了拷贝构造。
class Solution { public: vector<vector<int>> generate(int numRows) { if (numRows<=0) return vector<vector<int>> (); if (numRows==1){ return vector<vector<int>>(1, vector<int>(1,1)); } vector<vector<int>> out = generate(numRows-1); vector<int> cur_raw(numRows, 1); for (int i=1; i<numRows-1; ++i){ cur_raw[i] = out.back()[i] + out.back()[i-1]; } out.emplace_back(cur_raw); return out; } }; class Solution { private: void generate(int numRows, vector<vector<int>> &out){ if (numRows<=0) return; if (numRows==1){ out.emplace_back(vector<int>(1,1)); return; } generate(numRows-1, out); vector<int> cur_raw(numRows,1); for (int i=1; i < numRows-1; ++i){ cur_raw[i] = out.back()[i] + out.back()[i-1]; } out.emplace_back(cur_raw); } public: vector<vector<int>> generate(int numRows) { vector<vector<int>> out; generate(numRows, out); return out; } };