Pascal's Triangle

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]
]

Solution:
当前行的元素是上一行相邻两个元素相加的值，每行第一个和最后一个元素是1。
时间复杂度应该是O(1+2+3+...+n)=O(n^2)，空间上只需要二维数组来存储结果，不需要额外空间。

public class Solution {
    public ArrayList> generate(int numRows) {
        ArrayList> res = new ArrayList>();
        if(numRows == 0) 
            return res;
            
        ArrayList pre = new ArrayList();
        pre.add(1);
        res.add(pre);
        for(int i = 2; i <= numRows; i++) {
            ArrayList cur = new ArrayList();
            cur.add(1);
            for(int j = 0; j < pre.size() - 1; j++) {
                cur.add(pre.get(j) + pre.get(j + 1));
            }
            cur.add(1);
            res.add(cur);
            pre = cur;
        }
        return res;
    }
}