力扣第118题—杨辉三角

题目要求： 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

杨辉三角特点：

每一行的元素个数和行数是相同的，第一行一个元素，第二行两个元素...... 每一行的第一个元素和最后一个元素都是1 第三行的第二列等于第二行的第一列加第二列：[ 3,2 ] = [ 2,1 ] + [ 2,2 ]以此类推我们能得出下图规律

这个过程我们可以通过下面的动图直观的理解

代码实现：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//杨辉三角
public class LeetCode118 {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        //先写特殊的前两行
        List<Integer> fir = Arrays.asList(1);
        ret.add(fir);
        if (numRows == 1){
            return ret;
        }
        List<Integer> sec = Arrays.asList(1,1);
        ret.add(sec);
        if (numRows == 2){
            return ret;
        }

        //此时numRows至少为三
        //[i,j] = [ i -1 ,j -1 ] + [ i -1 ,j ]
        //i为行数，j为列数
        for (int i = 3; i <= numRows; i++) {
            //先取得前一行的所有元素
            //i-1表示前一行的行号，但是索引是从0开始的，所以需要再减1
            List<Integer> prev = ret.get(i-1-1);
            List<Integer> cur = new ArrayList<>();
            //加入第一行
            cur.add(1);
            //从第2列开始，到i-1列，也就是倒数第二列
            for (int j = 2; j < i; j++) {
                int tmpValue = prev.get(j-1-1) +prev.get(j-1);
                cur.add(tmpValue);
            }
            //每行最后一列为1
            cur.add(1);
            ret.add(cur);
        }
        return ret;

    }
}