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

tag: array

没什么算法技巧，了解帕斯卡三角的计算公式就好。不过也算是动态规划的一种吧。
1. A[i][j] = A[i – 1][j – 1] + A[i – 1][j]
2. A[i][1] = A[i][end] = 1

线性时间复杂度，常数空间复杂度。

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int>> re;
        if(numRows == 0){
            return re;
        }
        //first row
        vector <int> firstRow(1, 1);// row(count, value)
        re.push_back(firstRow);
        for(int i = 1; i < numRows; i++){
            vector<int> row;
            row.push_back(1);//first column
            for(int j = 1;j <= i; j++){
                if(j == i){//last column
                    row.push_back(1);
                }
                else{
                    row.push_back(re[i - 1][j] + re[i - 1][j - 1]);
                }
            }
            re.push_back(row);
        }
    
        return re;
    }
};