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?
解题思路1（实现巧妙，但时间复杂度高）：
空间复杂度O(k)，时间复杂度O(k^2)
和Pascal's Triangle类似，每一行数列，从后往前找规律：f(k)(n) = f(k-1)(n) + f(k-1)(n-1)
为了只使用O(k)空间，下一层数列可以在旧层数列基础上，从后往前更新。新一层已经更新的数字，不会影响到新一层中，还未更新的数字的计算。
代码：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + );
row[] = ;
for(int i = ; i <= rowIndex; i++)
for(int j = i; j >= ; j--)
if (j == i)
row[j] = row[j-];
else if (j == )
row[j] = row[j];
else
row[j] = row[j-] + row[j];
return row;
}
};
解题思路2（寻找公式，直接得出）：
空间复杂度O(k)，时间复杂度O(k)
根据数字规律，给出一个k，可以直接得到对应数列，不必通过前一个数列求值。
公式：
f(0) = 1;
f(n) = f(n-1)(k-n+1) / i n∈[1,k]
记录1(int越界出错)：
当k=30时，求出f(14)，要求f(15)时，由于要先乘（k-n+1）再除 i，因此做乘法时数值超出了int的最大范围+2147483647；
代码（未通过）：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + );
row[] = ;
for (int i=; i<=rowIndex; ++i) {
row[i] = row[i-] * (rowIndex-i+) / i;
}
return row;
}
};
修改（AC）：
将运算中的值暂时double，结果再转回int（12行）
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + );
row[] = ;
for (int i=; i<=rowIndex; ++i) {
row[i] = int(double(row[i-]) * double(rowIndex-i+) / i);
}
return row;
}
};
附录：
杨辉三角与计算机