LeetCode 118. 杨辉三角

◎

本节目标

从上一行构造下一行，在边界初始化为 1 后只递推内部位置。

这道题承接模拟、递推与边界：先给出每一行的边界，再从已经确定的上一行递推内部位置。

查看原题

题意与约束

给定整数 numRows，返回杨辉三角的前 numRows 行。第 0 行是 [1]；之后每一行的首尾都是 1，中间位置等于上一行相邻两个位置之和。

• 1 <= numRows <= 30
• 返回的第 row 行有 row + 1 个元素。

状态从哪里来

answer 保存已经构造好的所有行。处理第 row 行时，answer[row - 1] 已完整保存上一行，因此新行的每个内部位置都能直接读取它左上方和右上方的两个值。

循环结束后，answer 恰好包含从第 0 行到第 numRows - 1 行的所有结果。

边界先初始化为 1

每一行先创建长度为 row + 1、元素全为 1 的 current。这样首尾位置已经符合定义，也不会访问上一行不存在的相邻位置。

只有列号从 1 到 row - 1 的内部位置需要递推；第 0 列和最后一列没有左右两个前驱，不能套用中间位置的公式。

逐行递推过程

以下标为 3 的第 4 行（[1, 3, 3, 1]）为例，它从下标为 2 的第 3 行（[1, 2, 1]）构造而来：

下标为 3 的第 4 行位置	初始值或来源	得到的值
0	左边界，初始化为 1	1
1	下标为 2 的第 3 行的 1 + 2	3
2	下标为 2 的第 3 行的 2 + 1	3
3	右边界，初始化为 1	1

因此，每次先写好边界，再顺序填充内部位置即可。新行始终只读取已经完成的上一行，不会把本行刚写入的值误当作前驱。

代码实现

两份源码都逐行构造 current：边界初始化为 1，内部位置由上一行两个相邻值相加得到，随后把当前行加入 answer。

C++

C++17

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> answer;
        for (int row = 0; row < numRows; row++) {
            vector<int> current(row + 1, 1);
            for (int col = 1; col < row; col++) {
                current[col] = answer[row - 1][col - 1] + answer[row - 1][col];
            }
            answer.push_back(current);
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        answer = []
        for row in range(numRows):
            current = [1] * (row + 1)
            for col in range(1, row):
                current[col] = answer[row - 1][col - 1] + answer[row - 1][col]
            answer.append(current)
        return answer

复杂度分析

第 row 行有 row + 1 个元素，前 numRows 行的元素总数是二次量级。因此时间复杂度为 O(numRows²)；返回的三角形本身需要 O(numRows²) 输出空间。

易错点

• 让首尾位置也使用递推式，导致访问上一行越界。
• 忘记先把整行初始化为 1，使单元素行和边界行不正确。
• 从当前行读取前驱，混淆“上一行的状态”和“正在构造的状态”。
• 误把第 row 行写成长度 row，遗漏每行比上一行多一个元素的规律。

模式迁移

这是一类“新状态只依赖上一层”的构造问题。生成组合数、分层动态规划、按层创建二维表格时，都可以先确定边界或基例，再让内部状态读取已完成的上一层；遇到缺少前驱的位置，应优先单独初始化。