杨辉三角Java

什么是杨辉三角？

杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。

这样的三角形排列就被称为杨辉三角。

我们能发现一些规律：

1. 每一行的第一个元素和最后一个元素是1
2. 每一行除了第一个和最后一个元素，当前元素的值都为上一行的当前元素和前一个元素之和。

发现这些规律我们就可以写出我们的代码了。

public class Test {
    public List<List<Integer>> generate(int numRows) {
    	//numRows是打印出第几行
        List<List<Integer>> list = new ArrayList<>();
        if (numRows < 1) {
            //如果小于 1 行，直接返回
            return list;
        }

        //list 里面装的还是一个集合
        list.add(new ArrayList<>());
        //先添加一个1 相当于 [ [1] ]
        list.get(0).add(1);
        for (int i = 1; i < numRows; i++) {
            //要添加的新的一行
            List<Integer> row = new ArrayList<>();
            //保存要添加新的一行的上一行
            List<Integer> prevRow = list.get(i - 1);

            //先添加一个 1
            row.add(1);
            for (int j = 1; j < i; j++) {
                //添加上一行的当前位置元素和前一个元素的和
                row.add(prevRow.get(j - 1) + prevRow.get(j));
            }

            //添加每一行的最后一个 1
            row.add(1);
            //添加到集合中去
            list.add(row);
        }

        return list;
    }
}