1. Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,

Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

题意：这道题比较简单，在每一行的中间（除去最左最右），它的值等于上一行同列与上一行左一列之和。只需要考虑一些边界问题即可。

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        int i,j,index;
        vector<vector<int> > triangle;
        vector<int> line;
        if (numRows == 0)
        {
            return triangle;
        }
        line.push_back(1);
        triangle.push_back(line);
        if (numRows == 1)
        {
            return triangle;
        }    
        line.push_back(1);
        triangle.push_back(line);
        if (numRows == 2)
        {
            return triangle;
        }    
        for(i=2; i<numRows; i++)
        {
            line.clear();
            line.push_back(1);
            for(j=1; j<i; j++)
            {
                index = triangle[i-1][j-1] + triangle[i-1][j];
                line.push_back(index);
            }   
            line.push_back(1);
            triangle.push_back(line);    
        }   
        return triangle; 
    }
};

思路：这道题的计算公式为：

f[i][j] = f[i-1][j] + f[i-1][j-1] , i<j && i>0

f[i][j] = 1, i=0 || i=j

题目要求O(K)的空间复杂度，这时我们可以定义两个长度为K的数组，一个数组表示当前行的前一行数据，一个数组表示当前行的数据，再根据推导的公式即可写出代码。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> aa;
        vector<int> f;
        f.resize(rowIndex+1);
        aa.resize(rowIndex+1);
        int i,j;
        for(i=0; i<=rowIndex; i++)
        {
            f[0] = 1;
            f[i] = 1;
            for(j=1; j<i; j++)
            {
                aa[j] = f[j-1] + f[j];
            }
            aa[0] = f[0];
            aa[i] = f[i];
            f = aa;
        }
        return aa;
    }
};