Pascal Triangle

Description:

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]

]

Thoughts:
第一种：直观的想法就是，我们计算第n+1行的值，它的头尾都是1，中间的值T[n+1][i] = T[n][i-1]+T[i];根据这个想法得到如下的java代码：

class Solution {

        public List<List<Integer>> generate(int numRnows){

        List<List<Integer>> result = new ArrayList();

        if(numRnows<=0){

            return new ArrayList(){{}};

        }

        for(int i = 1;i<=numRnows;i++){

            List lists = new ArrayList();

            if(i == 1){

                lists.add(1);

            }else{

                lists.add(1);

                for(int j = 1; j<i-1;j++){

                    lists.add(result.get(i-2).get(j-1)+result.get(i-2).get(j));

                }

                lists.add(1);

            }

            result.add(lists);

        }

        return result;

    }

}

第二种想法：第i行有i个数；每次往最前面插入一个1，那么除了头尾以外，中间的值T[n][i] = T[n][i]+T[n][i+1], 根据这个想法得到如下的代码：

package easy.array;

import java.util.ArrayList;

import java.util.List;

public class GeneratePascal {

    public List<List<Integer>> generate(int numRnows){

        List<List<Integer>> allrows = new ArrayList<List<Integer>>();

        ArrayList<Integer> row = new ArrayList<Integer>();

        for(int i=0;i<numRnows;i++)

        {

            row.add(0, 1);

            for(int j=1;j<row.size()-1;j++)

                row.set(j, row.get(j)+row.get(j+1));

            allrows.add(new ArrayList<Integer>(row));

        }

        return allrows;

    }

    public static void main(String[] args){

        int numRnows = 10;

        GeneratePascal ge = new GeneratePascal();

        List<List<Integer>> f = ge.generate(numRnows);

        for(int i= 0; i<numRnows;i++){

            System.out.println(f.get(i));

        }

    }

}