Pascal’s Triangle II

Given an index k, return the k^th 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?

tags: array

动态规划中，如果我们只要某一行的规划矩阵的值，我们每必要存下整个矩阵，因为求解某一行的矩阵的值时我们只需要上一行矩阵的值（对于本题来说），所以我们只需记录上一行矩阵的值即可。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row;
        row.push_back(1);
        if(rowIndex == 0){
            return row;
        }
        else{
            vector<int> lastRow = row;
            for(int i = 1; i <= rowIndex; i++){
                row.clear();
                row.push_back(1);
                for(int j = 1; j < i; j++){
                    row.push_back(lastRow[j] + lastRow[j - 1]);
                }
                row.push_back(1);
                lastRow = row;
            }
            return row;
        }
    }
};