杨辉三角 图解题解

杨辉三角这道题到底要我们把什么填出来

给一个行数 numRows，摆出杨辉三角的前 numRows 行。它是个数字三角：第 0 行只有一个 1，往下每行多一个数，两端都是 1，中间每个数等于它「上一行」紧挨的两个数之和。题面给 numRows = 6，要返回前 6 行。后面说第 i 行第 j 个，行号 i、列号 j 都从 0 数起。

为什么照组合公式逐格算阶乘既慢又会溢出

杨辉三角第 i 行第 j 个数，其实就是组合数 C(i,j)（从 i 个东西里挑 j 个的取法数）。照定义每格单独算 C(i,j)=i!/(j!(i−j)!)，要反复乘阶乘（i! 就是 1×2×…×i），前面算过的又从头乘一遍。更麻烦的是阶乘涨得极快，行数稍大 i! 就冲破整数范围、乘出的大数会溢出，可那格的值明明不大，逐格硬算并不划算。

相邻两数相加背后是帕斯卡法则的组合直觉

换一个只用加法的算法，靠一条组合恒等式：C(i,j)=C(i-1,j-1)+C(i-1,j)。它说的是，从 i 个东西里挑 j 个，按「第 i 个选不选」分成两堆——不选它，从前 i-1 个里挑满 j 个，有 C(i-1,j) 种；选它，剩下的名额在前 i-1 个里挑 j-1 个，有 C(i-1,j-1) 种。两堆不重不漏加起来，正好是上一行紧挨的两个数之和，中间每格等于上方两数相加就是这么来的。

每行怎样从上一行推出，两端为何恒等于 1

有了这条法则，就能自底向上（从第 0 行起、每行只用刚填好的上一行往下推）逐行生成，不再碰阶乘。参考代码里每到第 i 行，先开一个长度 i+1 的 row、整排填 1；再让中间的 j 从 1 走到 i-1，把 row[j] 改成上一行的 res[i-1][j-1] 加 res[i-1][j]，也就是左上那个数加正上那个数。两端不进这轮修改，所以恒为 1。填完把 row 接到 res 末尾，留给下一行当依据。

拿 numRows = 6 亲手把六行填出来

第 0 行只有 1：[1]。第 1 行两端都是 1、没有中间格：[1,1]。第 2 行中间 1+1=2，得 [1,2,1]。第 3 行左边 1+2=3、右边 2+1=3，得 [1,3,3,1]。第 4 行 1+3=4、3+3=6、3+1=4，得 [1,4,6,4,1]。第 5 行 1+4=5、4+6=10、6+4=10、4+1=5，得 [1,5,10,10,5,1]。六行拼起来和题面输出逐格对上。

漏填两端的 1，最左格为什么会去够上一行不存在的邻居

三角形前 numRows 行一共约 numRows²/2 个数，每个数一次加法就填好，时间 O(n²)；这些数直接存进要返回的结果，空间也是 O(n²)。两处边界最容易出岔。第 0 行只有一格，中间那圈 j 从 1 到 i-1 不进，全靠「整排先填 1」兜住，漏了这步第一行就空着。两端的 1 同理：要是让 j 从 0 扫到 i，改最左格会取到上一行并不存在的左邻居，不是越界就是算错。

Python

def generate(numRows):
    res = []
    for i in range(numRows):
        row = [1] * (i + 1)
        for j in range(1, i):
            row[j] = res[i-1][j-1] + res[i-1][j]
        res.append(row)
    return res

C++

vector<vector<int>> generate(int numRows){
    vector<vector<int>> res(numRows);
    for(int i = 0; i < numRows; i++){
        res[i].assign(i + 1, 1);
        for(int j = 1; j < i; j++)
            res[i][j] = res[i-1][j-1] + res[i-1][j];
    }
    return res;
}

Java

List<List<Integer>> generate(int numRows){
    List<List<Integer>> res = new ArrayList<>();
    for(int i = 0; i < numRows; i++){
        List<Integer> row = new ArrayList<>();
        for(int j = 0; j <= i; j++){
            if(j == 0 || j == i) row.add(1);
            else row.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
        }
        res.add(row);
    }
    return res;
}