What is the core pattern used in Pascal's Triangle problem?

The main pattern is state transition dynamic programming, where each row is derived from the previous by summing adjacent elements.

Can Pascal's Triangle be generated recursively?

Yes, but recursion without memoization is inefficient and can lead to repeated computations; iterative DP is preferred.

How do I handle the first and last elements in each row?

Always set the first and last elements to 1 explicitly; only sum elements in between using the previous row.

What is the time complexity of generating numRows rows?

Time complexity is O(numRows^2) since row i has i elements and each element is computed once.

Is it possible to optimize space while generating Pascal's Triangle?

Yes, by keeping only the previous row to compute the current row, space can be reduced to O(numRows).

#118

Easy

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

杨辉三角

给定一个非负整数 numRows ，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2: 输入: nu…

数组动态规划

题目描述

给定一个非负整数 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

lightbulb

解题思路

方法一：模拟

我们先创建一个答案数组 $f$ ，然后将 $f$ 的第一行元素设为 $[1]$ 。接下来，我们从第二行开始，每一行的开头和结尾元素都是 $1$ ，其它 $f[i][j] = f[i - 1][j - 1] + f[i - 1][j]$ 。

时间复杂度 $O(n^2)$ ，其中 $n$ 为给定的行数。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        f = [[1]]
        for i in range(numRows - 1):
            g = [1] + [a + b for a, b in pairwise(f[-1])] + [1]
            f.append(g)
        return f

speed

复杂度分析

指标	值
时间	complexity is O(numRows^2) because each row i contains i elements, and we compute each sum once. Space complexity is O(numRows^2) if storing all rows, or O(numRows) if only keeping the previous row for computation.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks if you can explain why each element is the sum of the two above.
question_mark
Wants a clear iterative or dynamic programming solution, not recursion.
question_mark
May probe how you handle boundaries or optimize space for large numRows.

warning

常见陷阱

外企场景

error
Forgetting to place 1 at the start and end of each row.
error
Incorrectly summing elements causing off-by-one errors in the triangle.
error
Attempting recursion without memoization, leading to unnecessary complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generate only the nth row without constructing the full triangle using optimized DP.
arrow_right_alt
Return Pascal's Triangle modulo a given number for very large values.
arrow_right_alt
Compute triangle diagonals or specific positions efficiently using combinatorial formulas.

help

常见问题

外企场景

继续练习

#119 杨辉三角 II #120 三角形最小路径和 #121 买卖股票的最佳时机