119. Pascal's 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?

如果像之前那样采用使用上一行直接生成下一行的办法：

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    if (rowIndex===0) 
        return [1];
    if (rowIndex===1)
        return [1,1];
    var pre = [1,1];
    var now = [];
    for (var i =2; i <= rowIndex; i++) {
        now[0]=1;
        for (var j = 1;j<i;j++) {
            now[j] = pre[j-1] + pre[j];
        }
        now[i] = 1;
        pre = now;
        now = [];
    }
    return pre;
};

这种办法并不满足O（k）的空间要求，因为要同时保存2行的信息。
那么就要寻找一种直接在行内生成下一行的办法：

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    var row = [];
    row[0] = 1;
    for (var k =1;k<rowIndex+1;k++) {
        row[k] = 0;
    }
    for(var i=1; i<row.length; i++) {
        for(var j=i; j>=1; j--) {
            row[j] += row[j-1];
        }
    }
    return row;
};

我们创建一个元素数量与最后结果相同的数组，假设参数为4:
[1,0,0,0,0]
从最后一个元素开始，本元素等于本元素和前一个相加，
[1,1,0,0,0]
[1,2,1,0,0]
[1,3,3,1,0]
[1,4,6,4,1]