刷 LeetCode 的人应该都见过 118. 杨辉三角这道题虽然标着 Easy却是我面试时被问过最多的一道“伪简单题”。它表面上只是生成一个三角形数组可背后的动态规划思路、边界处理和空间优化几乎能从小白一路问到资深岗。很多人刷完 118 觉得太简单转头在 119. 杨辉三角 II 或者面试官追问“能不能只用 O(n) 空间”的时候又卡住。所以我想把杨辉三角的编程思路完整拆一遍从题目边界、状态转移、不同写法到组合数、滚动数组、力扣热题 100 里常见的变种一次性讲透。这篇文章适合刚入门想搞懂二维列表递推的新手也适合准备跳槽想快速过一遍高频题的朋友。1. 题目在说什么输入输出、示例和最容易看走眼的边界1.1 先建立最基础的画面感题目会给一个非负整数numRows要求返回杨辉三角的前numRows行。力扣的示例是numRows 5返回[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]注意这里每一行是一个ListInteger整体是一个二维列表。题目描述里出现一个很容易被忽略的词非负整数。也就是说numRows可以等于 0等于 0 时返回空列表[]而不是[[]]更不是[[1]]。这个边界很多人在笔试时没看仔细白白送掉一个测试用例。1.2 “第 0 行”这个索引陷阱坑过很多人我在自己刷题群里面见过不少朋友把第一行写成[1, 1]然后从第二行开始循环。这么写不是不行但很容易让后面的逻辑分成“第一行特殊处理”和“其余行正常处理”两段代码变丑不说还容易在numRows 1的时候出 bug。其实力扣定义的“第 0 行”就是[1]第 1 行才是[1, 1]。我们从第 0 行开始逐行利用上一行生成下一行这样逻辑最统一先处理第 0 行后面每行都由前一行递推得到不需要再额外做分支。1.3 边界条件里的“隐藏选项”除了numRows 0还有一个隐藏选项是numRows 1。如果代码里先初始化一个result []然后for i in range(numRows)在循环里给row赋值[1] * (i 1)那么i 0时自然得到[1]i 1时得到[1, 1]完全不需要手动处理。很多人会单独写if numRows 1: return [[1]]其实没必要。我建议一开始就按照“第 0 行是 [1]”的直觉来写后面所有索引都能对得上。提示力扣的测试用例里numRows 0时要求返回[]不是空二维列表。写代码前先把这个特判想清楚否则报错后会浪费很多排查时间。2. 从数学到代码杨辉三角的两个核心生成规则2.1 动态规划的状态转移方程是怎么从图形里“长”出来的杨辉三角最经典的生成规则只有一句话每个数等于它左上方和右上方的两个数之和。如果定义一个二维数组dp[i][j]表示第i行第j列从 0 开始计数那么状态转移方程就是dp[i][j] dp[i-1][j-1] dp[i-1][j]但这里有个前提dp[i-1][j-1]和dp[i-1][j]必须存在。对第i行的首尾元素来说dp[i-1][-1]和dp[i-1][i]是不存在的所以通常我们把首尾直接设为 1。这也是为什么很多解法里会先写row[j] 1 if j 0 or j i else prev[j-1] prev[j]。理解了这点就理解了这道题 90% 的动态规划逻辑。2.2 首尾的 1 为什么不能硬套公式有人会问既然首尾元素按转移方程也应该是dp[i-1][j-1] dp[i-1][j]那能不能给“不存在的位置”补 0然后统一按公式算比如把上一行的左边界外看作 0右边界外也看作 0那么dp[i][0] 0 dp[i-1][0] 1同样能得到 1。这个思路没错很多“补零”的优雅写法就是这样来的。但在面试时如果你用if判断首尾代码会更容易读也更好向面试官解释。我个人的建议是平时刷题追求简洁可以用补零技巧但面试时最好用最直观的“首尾赋 1 中间递推”省得面试官追问边界时你还要解释补零为什么不会出错。2.3 组合数 C(n,k) 和逐行递推的关系学过排列组合的同学知道杨辉三角第n行第k个元素的值其实等于组合数C(n, k)。比如第 4 行是[1, 4, 6, 4, 1]分别对应C(4,0)到C(4,4)。逐行递推本质上是在用加法计算组合数避免了阶乘和除法可能带来的溢出。反过来如果题目只需要某一行就可以用组合数公式在O(n)时间内直接算出来而不必生成前面所有行。这两个视角一个是动态规划一个是数学公式各有适用场景。力扣 118 本身要求返回整个三角形所以递推是更贴合题意的解法但理解组合数的关系对后面做 119 题和面试中的拓展非常有用。3. 最小可用实现Python 解法从零到一3.1 第一版代码照着状态转移方程写先把最直白的写法放出来。这个版本完全按照“上一行相邻两数相加”的思路适合刚接触动态规划的人理解class Solution: def generate(self, numRows: int) - List[List[int]]: if numRows 0: return [] result [] for i in range(numRows): row [1] * (i 1) # 把整行先填成 1首尾自然满足 if i 2: prev result[i - 1] for j in range(1, i): row[j] prev[j - 1] prev[j] result.append(row) return result这里range(1, i)是关键。第i行有i 1个元素索引从 0 到i。我们已经让首尾保持 1中间元素索引就是1到i - 1所以循环范围是range(1, i)。有些新手会写成range(1, i 1)结果最后一个中间位置越界也有人写成range(i)又把首元素重复算了一遍。别小看这个循环范围我真见过不少人在这一行上面反复试错。3.2 更短的生成式写法每行由上一行“错位相加”如果追求代码简洁可以用列表推导式。上一行是prev中间元素就是prev[j] prev[j 1]最后在首尾各加 1class Solution: def generate(self, numRows: int) - List[List[int]]: if numRows 0: return [] result [[1]] for i in range(1, numRows): prev result[-1] row [1] [prev[j] prev[j 1] for j in range(len(prev) - 1)] [1] result.append(row) return result这个写法把“首尾 1 中间相邻和”直接表达出来了。len(prev) - 1是因为上一行有len(prev)个元素相邻两两相加能得到len(prev) - 1个中间值再加上首尾两个 1正好凑成新一行的长度。两种写法复杂度完全一样选哪种主要看你对可读性的偏好。我平时在编辑器里喜欢用第二种因为省事但面试手写时我会用第一种减少推导语法的时间。3.3 复杂度分析面试时怎么答才完整这道题的时间复杂度是O(numRows²)因为最终返回的三角形里一共包含n(n1)/2个元素每个元素都生成一次所以总和是平方级别。空间复杂度要分两层说如果只算额外辅助空间不考虑返回值那么额外空间只有prev这样一个引用可以认为是O(1)如果算上要返回的二维数组那自然是O(numRows²)。面试时如果被问“空间复杂度是多少”建议主动说清楚这个区分同时补一句“因为题目要求返回所有行这个二维数组是必须的”。很多时候面试官就在等这句话它能体现你对空间占用的真实理解而不是背答案。4. 滚动数组和空间优化面试官一定会追问的点4.1 只保留上一行把二维压成一维力扣 118 要返回整个三角形所以二维数组没法省。但面试官经常考一个变种如果只要第rowIndex行你能不能用O(rowIndex)的空间完成答案是“滚动数组”。我们不需要保存所有历史行只需要上一行来计算当前行计算完就把当前行变成新的上一行。这样空间从平方级降到线性级。class Solution: def getRow(self, rowIndex: int) - List[int]: row [1] for i in range(1, rowIndex 1): next_row [1] * (i 1) for j in range(1, i): next_row[j] row[j - 1] row[j] row next_row return row这里next_row[j] row[j-1] row[j]用的还是旧行row因为新行还没有覆盖旧行。这种“用一个变量滚动更新”的思想在动态规划里非常常见尤其是二维 DP 压缩成一维 DP 时几乎每次都会用到。4.2 原地更新时为什么要从后往前还有一种更省空间的写法直接用一维数组原地更新不用额外的新列表。比如生成第rowIndex行可以这样写row [1] * (rowIndex 1) for i in range(2, rowIndex 1): for j in range(i - 1, 0, -1): row[j] row[j - 1]这里内层循环必须从后往前遍历。为什么因为row[j]的更新依赖的是上一行在j和j-1位置的值也就是旧值。如果从前往后遍历row[j-1]已经被本行更新过了再拿来算row[j]就会得到错误结果。举个小例子第 2 行从上一行[1,1]生成[1,2,1]如果从前往后先算row[1] row[0]row[1]变成 2再算row[2] row[1]时用的是 2 而不是原来的 1最后得到 3明显不对。所以“原地更新”和“倒序遍历”是绑定的这个点被问到的概率极高建议记牢。4.3 一行代码生成下一行Python 里的 zip 技巧Python 里有一个很优雅的写法把上一行和它的错位版本对齐用zip把对应元素加起来。比如上一行是[1, 2, 1]下一行的中间部分是[12, 21]也就是row [1] [a b for a, b in zip(prev, prev[1:])] [1]zip(prev, prev[1:])会依次把prev[0]和prev[1]、prev[1]和prev[2]组合起来正好生成所有相邻元素对。这个写法很 Pythonic但如果你不熟悉列表推导式建议先在草稿纸上画出prev和prev[1:]的对应关系理解后再用。刷题写这种代码确实快但正式面试时我会先写常规循环再提一句“Python 里可以用 zip 写得更短”展示你有多余的思路。5. 除了 118力扣还藏着哪些“杨辉三角变种”5.1 119. 杨辉三角 II如何只返回指定行力扣会有一个姊妹题 119. 杨辉三角 II题目会给一个rowIndex返回杨辉三角的第rowIndex行。注意索引从 0 开始所以rowIndex 3返回[1, 3, 3, 1]。最直观的解法就是用滚动数组逐行生成不需要保留前面所有行。也就是 4.1 节那段代码。它的时间复杂度O(rowIndex²)空间O(rowIndex)。对于这道题面试官很可能希望听到你用组合数公式做到O(rowIndex)时间这就会引出下一个点。5.2 组合数终极解法O(k) 时间搞定指定行如果用组合数公式第rowIndex行也就是数学上的第n行n rowIndex的第k个元素是C(n, k)并且相邻两项之间有递推关系C(n, k) C(n, k-1) * (n - k 1) / k用这个公式可以从左到右依次算出整行不用依赖上一行。下面是 Python 实现class Solution: def getRow(self, rowIndex: int) - List[int]: n rowIndex res [1] * (n 1) for k in range(1, n 1): res[k] res[k - 1] * (n - k 1) // k return res这里有个小细节一定要先乘后除因为res[k-1] * (n-k1)的结果一定可以被k整除组合数本身就是整数如果先除再乘在k不能整除n-k1时就会得到小数或错误结果。在 Python 里//是整除先乘后除能保证精确。如果是 C 或 Java中间变量res[k-1] * (n-k1)可能溢出需要用long类型这也是面试中常被追问的坑。力扣 119 要求的rowIndex最大是 33所以直接乘不溢出但面试官会习惯性问一句“数字大了怎么办”。5.3 把杨辉三角和动态规划入门路径串起来在力扣热题 100 里118 往往被放到动态规划专题的入门位置。它的核心价值在于让你体会三件事定义状态、找到转移方程、处理边界。如果这三步你都走顺了后面再做 120. 三角形最小路径和会发现逻辑很像从三角形的顶部开始每个位置选择下方相邻路径中较小的值同样是从上往下递推。区别在于 118 是“上往下相加”120 是“下往上取最小”。建议刷完 118 和 119 后顺手把 120 也做了这样你对二维递推的敏感度会明显提升。我自己带过几个新人让他们按这个顺序刷普遍反馈比单独刷一道题效果好得多。6. 笔试和面试中常踩的坑经验篇6.1 numRows0 到底返回什么用代码先写出来前面反复提过numRows0时返回[]这里再强调一下有些同学会写成return [[]]然后被测试用例打脸。更稳妥的做法是在方法一开始就写if numRows 0: return []不要自己脑补“空三角就是[[]]”。力扣题目明确要求返回空列表所以你只需要照做。如果你担心函数里多个返回分支看起来乱也可以用result []然后循环里if not result: result.append([1])但显然第一种最直接。6.2 内层循环的索引为什么容易写错我最常看到的新手错误是内层循环写成for j in range(i 1)然后在循环里用if j 0 or j i判断首尾。这个写法逻辑上没问题但写的行数较多容易在prev[j] prev[j 1]时不小心越界。更推荐先row [1] * (i 1)让首尾自动是 1然后只循环中间位置range(1, i)。这样索引范围非常清晰第i行中间元素是1到i - 1一共i - 1个。还有一个容易错的地方是下标对应关系。当前行的第j个元素左上方是上一行的j - 1右上方是上一行的j。虽然加法交换律让prev[j-1] prev[j]和prev[j] prev[j-1]结果一样但如果你在更复杂的 DP 里写反了可能就会用错数据。注意培养这种“位置感”。6.3 别在 118 上用组合数公式画蛇添足偶尔会看到有人用组合数公式直接从头生成每一行也就是对每一行的每个元素都算一次C(n,k)。如果实现时每个组合数都用阶乘算时间复杂度会变成O(n³)而且还有溢出的风险。即使你聪明到用递推公式一行一行地算也完全没有利用到上一行的已有结果失去了这道题想考察的动态规划意义。刷题并不仅仅是让代码通过还要考虑这道题希望你掌握什么。我个人实际面试时如果候选人一上来就在 118 上讲组合数公式我会追问“如果我要整个三角形逐行递推更简单还是组合数更简单”不少人会答错。所以我的建议是118 用递推119 再用组合数优化别混着用。最后分享一下我自己的刷题习惯做完一道 Easy 题不要急着 Next先想三件事——边界条件有哪些、空间能不能压缩、能不能用数学公式换一种解法。杨辉三角正好三道题串下来能把这三点都覆盖。如果你也刷到 118建议顺手把 119 和 120 一起做了等做完了你会发现动态规划里最常见的“从上往下、从左往右”递推其实就这么回事。