题目链接：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?
这道题的要求是生成杨辉三角的第k行。
和Pascal’s Triangle类似，同样是生成杨辉三角。同样利用每个数字等于上一行的左右两个数字之和逐行生成杨辉三角。由于要求空间复杂度O(k)，因此需要只存储杨辉三角中的一行即可。由于C(n+1,i) = C(n,i) + C(n,i-1)，因此在生成杨辉三角的某行时，可以从后往前进行，这样就可以不会覆盖到前面的结果了。
时间复杂度：O(n2)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution
{
public:
vector<int> getRow(int rowIndex)
{
// 首先令所有值都为1，这样两端的1就直接生成了
vector<int> vi(rowIndex + 1, 1);
for(int i = 1; i <= rowIndex; ++ i)
for(int j = i - 1; j > 0; -- j) // 从后往前
vi[j] += vi[j - 1];
return vi;
}
};