1.4 118 Pascal's Triangle Leetcode

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

每個數是它左上方和右上方的數的和(from Wiki)

巴斯卡三角的規律是

1. 第k層有k個原素
2. 每層第一個及最後一個元素值為1
3. 對於K > 2層第n元素值為A[k][n]=A[k-1][n-1]+[k-1][n]。

int** generate(int numRows, int** columnSizes) {
    if (numRows <= 0) {
        *columnSizes = NULL;
        return NULL;
    }

    int* columns = (int*)malloc(sizeof(int) * numRows);
    columns[0] = 1;

    int** pascal = (int**)malloc(sizeof(int*) * numRows);
    pascal[0] = (int*)malloc(sizeof(int));
    pascal[0][0] = 1;

    for (int i = 1; i < numRows; ++i) {
        columns[i] = i + 1;
        pascal[i] = (int*)malloc(sizeof(int) * columns[i]);

        pascal[i][0] = 1;
        for (int j = 1; j < i; ++j) {
            pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
        }
        pascal[i][i] = 1;
    }

    *columnSizes = columns;
    return pascal;
}