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

S: simple for loop O(n^2)

vector<vector<int>> generate(int numRows) {
  vector<vector<int>> result;
  if(numRows == 0) return result;
  result.push_back(vector<int>{1});
  for(int row = 1; row < numRows; ++row){
      vector<int> newRow(row+1, 1);
      for(int i = 1; i < row; ++i) newRow[i] = result[row-1][i-1]+result[row-1][i];
      result.push_back(newRow);
  }
  return result;
}

119. Pascal Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3,3,1].

Note: Could you optimize your algorithm to use only O(k) extra space?

S：只需要记录倒数第二行的值即可

vector<int> getRow(int rowIndex) {
    vector<int> result(rowIndex+1, 1);
    vector<int> preRow(rowIndex, 1);
    for(int row = 1; row <= rowIndex; ++row){
        preRow = result;//因为第二层循环改变了result的值，需要额外数组来记录原来的值
        for(int i = 1; i < row; ++i){
          result[i] += preRow[i-1];
        }
    }
    return result;
}

若是第二层循环从后往前，可以不用额外空间记录上一行，因为从前往后每次改动的是resul[i-1],而从后往前每次改动的是result[i+1]，不会影响结果。

vector<int> getRow(int rowIndex) {
    vector<int> result(rowIndex+1, 1);
    for(int row = 1; row <= rowIndex; ++row){
        for(int i = row-1; i > 0; --i) result[i] += result[i-1];
    }
    return result;
}