118. Pascal's Triangle

算法：Dynamic Programming.
时间复杂度：O(numRows *numRows ）
空间复杂度O(numRows *numRows ）

 public List<List<Integer>> generate(int numRows)
    {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();
        //如果为空，返回
        if (numRows <= 0)
        {
            return triangle;
        }

        //第一行为1
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int i = 1; i < numRows; i++)
        {
            List<Integer> nowRow = new ArrayList<Integer>();
            List<Integer> preRow = triangle.get(i - 1);

            //每组开始为1
            nowRow.add(1);
            for (int j = 1; j < i; j++)
            {
                nowRow.add(preRow.get(j - 1) + preRow.get(j));
            }
            //每组最后为1，不然会发生越界
            nowRow.add(1);
            triangle.add(nowRow);
        }
        return triangle;
    }