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?

题目大意:

题目要求杨辉三角形的某一行，当然可以把每一行都求出来然后输出要求的行。

但是题目要求不能这样做。

每一行的元素都是依赖上一行元素的。并且每一行都比上一行多一个元素。如果我们按照从前往后的顺序递推更新，由于每个元素依赖当前列和前一列的元素，因此前面的元素更新必然会影响后面元素的结果，这是我们不想见到的。

那么应该如何解决这个问题呢。我们可以尝试从后面开始更新，因为每个元素依赖当前列和前一列，因此后一列元素更新不会影响到前面元素。有一道题和这个思路很像可以尝试练习点击打开链接

题目代码:

class Solution {
public:vector<int> getRow(int rowIndex) {vector<int>v(rowIndex+1);v[0] = 1;if(rowIndex == 0) return v;v[1] = 1;if(rowIndex == 1) return v;for(int i = 2; i <= rowIndex; i++){for(int j = i; j > 0; j--){v[j] = v[j] + v[j-1];}}return v;}
};