118. 杨辉三角

力扣题目链接 (opens new window)

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1：

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2：

输入: numRows = 1
输出: [[1]]

提示：

• 1 <= numRows <= 30

思路

杨辉三角是经典的动态规划问题，因为每个位置的值都是由上一行相邻位置决定的。

先看暴力思路：直接用组合数公式 C(n, k) 计算每个位置的值。但组合数计算涉及阶乘，容易溢出，而且时间复杂度也不够优化。

其实杨辉三角有一个非常直观的规律：每一行的首尾都是 1，中间的数等于上一行相邻两数之和。

这就是典型的动态规划思路！

那么我们按照动规五部曲来分析：

1. 确定 dp 数组及下标含义

这里 dp 数组就是结果本身，result[i][j] 表示第 i 行第 j 个位置的值（从 0 开始计数）。

2. 确定递推公式

根据杨辉三角的规律：

• 每行的首尾：result[i][0] = result[i][i] = 1
• 中间的数：result[i][j] = result[i-1][j-1] + result[i-1][j]

3. dp 数组初始化

第一行只有一个 1：result[0] = [1]

4. 确定遍历顺序

必须从上往下逐行构建，因为当前行依赖上一行的结果。

5. 举例推导 dp 数组

这部分放在"模拟过程"中详细说明。

模拟过程

以 numRows = 5 为例，逐行构建：

第 0 行（初始化）：

[1]

第 1 行： 首尾都是 1，无中间元素

[1, 1]

第 2 行：

• 首尾是 1
• 中间：result[1][0] + result[1][1] = 1 + 1 = 2

[1, 2, 1]

第 3 行：

• 首尾是 1
• 中间第 1 个：result[2][0] + result[2][1] = 1 + 2 = 3
• 中间第 2 个：result[2][1] + result[2][2] = 2 + 1 = 3

[1, 3, 3, 1]

第 4 行：

• 首尾是 1
• 中间第 1 个：result[3][0] + result[3][1] = 1 + 3 = 4
• 中间第 2 个：result[3][1] + result[3][2] = 3 + 3 = 6
• 中间第 3 个：result[3][2] + result[3][3] = 3 + 1 = 4

[1, 4, 6, 4, 1]

drawio 提示词：画 5 行杨辉三角的构建过程，第一张图展示前 3 行的构建和箭头指向，第二张图展示第 4 行如何从第 3 行推导而来，标注 1+3=4、3+3=6、3+1=4 的计算过程。画布统一，Logo 放左下角。

文件名：

• 0118.pascals-triangle-01-build-rows.drawio
• 0118.pascals-triangle-02-row4-calculation.drawio

解题代码

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result(numRows); // 预分配 numRows 行
        
        for (int i = 0; i < numRows; i++) {
            result[i].resize(i + 1); // 第 i 行有 i+1 个元素
            result[i][0] = result[i][i] = 1; // 首尾都是 1
            
            for (int j = 1; j < i; j++) { // 中间元素
                result[i][j] = result[i-1][j-1] + result[i-1][j];
            }
        }
        
        return result;
    }
};

复杂度分析

• 时间复杂度：O(numRows²)，需要填充所有位置，总共有 1+2+3+...+numRows = numRows*(numRows+1)/2 个元素
• 空间复杂度：O(1)，不考虑返回值的话只用了常数额外空间

其他语言

Python3

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = []
        
        for i in range(numRows):
            row = [1] * (i + 1)  # 先全部初始化为 1
            
            for j in range(1, i):  # 只需处理中间元素
                row[j] = result[i-1][j-1] + result[i-1][j]
            
            result.append(row)
        
        return result

Java

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = 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); // 首尾是 1
                } else {
                    row.add(result.get(i-1).get(j-1) + result.get(i-1).get(j));
                }
            }
            
            result.add(row);
        }
        
        return result;
    }
}

Go

func generate(numRows int) [][]int {
    result := make([][]int, numRows)
    
    for i := 0; i < numRows; i++ {
        result[i] = make([]int, i+1)
        result[i][0], result[i][i] = 1, 1 // 首尾是 1
        
        for j := 1; j < i; j++ { // 中间元素
            result[i][j] = result[i-1][j-1] + result[i-1][j]
        }
    }
    
    return result
}

JavaScript

var generate = function(numRows) {
    const result = [];
    
    for (let i = 0; i < numRows; i++) {
        const row = new Array(i + 1).fill(1); // 初始化为 1
        
        for (let j = 1; j < i; j++) { // 中间元素
            row[j] = result[i-1][j-1] + result[i-1][j];
        }
        
        result.push(row);
    }
    
    return result;
};

与代码随想录联系

杨辉三角是动态规划入门的经典题目，它的递推关系非常直观。

如果录友们想系统学习动态规划，建议先看代码随想录的动态规划章节，从 509. 斐波那契数 和 70. 爬楼梯 开始，逐步建立动规思维。

杨辉三角和爬楼梯的递推思路类似，都是"当前状态由前面状态推导而来"，只不过杨辉三角是二维的，依赖的是上一行的两个相邻位置。