118 Pascal's Triangle

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]
]

Solution

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if ( numRows == 0 ) return res;
        for ( int i = 0; i <= numRows-1; i++ ) {
            vector<int> tmp1(1, 1);
            int i1 = i, i2 = 1;
            while ( i1 >= 1) {
                int n = tmp1[tmp1.size()-1];
                tmp1.push_back(n*(i1--)/(i2++));
            }
            res.push_back(tmp1);
        }
        return res;
    }
};

Notes Note the following relation:

• $$res[i][j] = C_{(i)}^{(j)}$$
• $$C{i}^{j} = \frac{i+1-j}{j}C{i}^{j-1} $$

while ( i1 >= 1) {
  int n = tmp1[tmp1.size()-1];
  tmp1.push_back(n*(i1--)/(i2++));
}