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

For example, given numRows = 5,

Return

[     [1],    [1,1],   [1,2,1],  [1,3,3,1], [1,4,6,4,1]]

解题思路1：迭代插入（未通过）

[              [               [                      [     [1],           [1],            [1],                   [1],    [1],           [1,1],          [1,1],                 [1,1]   [1],   ==>     [1,2],  ==>     [1,2,1], ==>...==>     [1,2,1],  [1],           [1,3],          [1,3,3],               [1,3,3,1], [1]            [1,4]           [1,4,6],               [1,4,6,4,1],]              [               [                      [

可以推导出每一列的递推公式：

第一列从第一行开始：1                                                                            

第二列从第二行开始：j / 1,  j∈[1,n)

第三列从第三行开始：[j*(j-1)] / [1*2], j∈[2,n)

...

第M列从第M行开始：[j*(j-1)*...*(j-m+2)] / [1*2*...*m-1], j∈[m,n)

但是程序未能实现，在输入numRows=8时，出现Runtime Error错误。

 

【★】解题思路2：

用f(n)(m)表示第n行第m个元素，n从1开始，1≤m≤n；

则f()(1)=f()(n)=1, f(n)(m)=f(n-1)(m-1) + f(n-1)(m);

核心代码只有四步：

①新建符合的空间；

②将首尾置为1；

③遍历除首尾外的元素空间，利用公式填充；

④将填充好的列表放入结果队列里；

 

1 class Solution { 2 public: 3     vector
     
      
        > generate(int numRows) { 4         vector
       
        
          > rowslst; 5          6         if (numRows == 0) 7             return rowslst; 8          9         for (int i=0; i
         

row(i+1); 11 row[0] = row[i] = 1;12 13 for(int j=1; j