[Trianlge]Pascal's Triangle

1. Example
numRows = 5
return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]


2. Implementation
cur[i] = prev[i] + prev[i-1], i > 0 and i < len-1
keep previous list
NOTE:
cur.add(1); 

for (int i = 0 ;i < pre.size() -1; i ++ ) {

 cur.add( pre.get(i) + pre.get(i+1) ); 

}

 cur.add(1);

// Time:O(1+2+3+..+n) = O(n^2), Space:O(n) List>

public List> generate(int numRows) 
{
      List> res = new ArrayList>();
     // validate the input
     if (numRows <= 0 )
     {
          return res;
     }
 


     List pre = new ArrayList();
     pre.add(1);
     res.add(pre);



     for ( int j = 2 ; j < numRows ; j++ )


         // form certains row's list 
         List cur = new ArrayList();
         cur.add(1);
         for (int i = 0 ;i < pre.size() -1; i ++ )
         {
            cur.add( pre.get(i) + pre.get(i+1)  ); 
         }
         cur.add(1);



         res.add(cur);
         pre = cur;

     }
     return res;

}

3. Similar Ones
(E) Pascal's Triangle II