很多人刷力扣刷到杨辉三角这道题时第一反应是“这不就是两重for循环嘛有什么好讲的”。我最初也是这么想的直到后来在力扣热题100里重新做这道题才意识到它其实是理解动态规划Dynamic Programming最好的“最小样本”之一。标题里的“82”可能是某个刷题清单里的编号也可能指的是力扣上的118题但无论编号怎么变核心只有一个用动态规划的方式生成杨辉三角。这篇文章我会把这道题从二维数组的常规解到滚动数组的倒推优化再到它和组合数、其他DP题目之间的关系完整拆开讲一遍希望能帮那些刚接触DP的同学少走弯路。1. 一道“简单题”为什么值得用动态规划的角度重做一遍1.1 从杨辉三角的构造规则说起先回忆一下定义杨辉三角的第0行或者第1行看你习惯哪种下标只有一个数字1第1行是1 1第2行是1 2 1第3行是1 3 3 1。规律是每一行的首尾都是1中间每个数字等于它左上方和右上方的数字之和。写成数学递推式就是dp[i][j] dp[i-1][j-1] dp[i-1][j]其中i表示行j表示列且边界位置j 0或j i时为1。这个规律看起来简单但它恰好具备动态规划的所有要素有“子问题”前一行的数值有“状态转移方程”上面的递推式有“初始条件”第一行是1。所以它和爬楼梯、斐波那契数列一样是入门DP最友好的题目之一。不过杨辉三角比斐波那契更进阶的点在于它不是一个一维序列而是一个二维三角结构状态之间不是简单的线性依赖而是有“上一行相邻两个位置”的依赖关系。理解了这个二维依赖后面再看什么路径问题、编辑距离思路都会顺畅很多。1.2 动态规划三要素在这个问题上如何落地很多同学学DP时最头疼的是“我怎么知道这道题用DP”“状态怎么定义”杨辉三角提供了一个极其直观的答案。状态定义dp[i][j]表示杨辉三角第i行第j列的数字。状态转移除了左右边界dp[i][j] dp[i-1][j-1] dp[i-1][j]。这个转移是严格“从上一行推向下一行”的天然满足DP的无后效性。初始化第0行只有一个元素dp[0][0] 1。每一行的首尾都要单独赋值为1。如果你把dp表格画出来会发现每一行的计算只依赖上一行所以既可以用二维数组保存完整的历史结果也可以只用一维数组滚动更新。后者正是很多“优化空间复杂度”的题解里提到的做法也是这道题进阶的核心。2. 常规解二维dp逐行填充先跑通再说2.1 代码实现Python / C如果你刚开始刷题不需要急着优化先把最直接的二维dp写出来。以 LeetCode 118 题“杨辉三角”为例它要求返回整个三角形即一个List[List[int]]。Python 实现如下def generate(numRows: int): dp [] for i in range(numRows): row [1] * (i 1) # 先全部填1左右边界天然正确 for j in range(1, i): row[j] dp[i - 1][j - 1] dp[i - 1][j] dp.append(row) return dp这段代码的核心是每一行先创建长度为i1的全1数组这样首尾就不需要额外赋值。中间位置j从1遍历到i-1不包括最后一个用上一行的两个数相加。最后把当前行加入dp。C 版本类似vectorvectorint generate(int numRows) { vectorvectorint dp; for (int i 0; i numRows; i) { vectorint row(i 1, 1); for (int j 1; j i; j) { row[j] dp[i - 1][j - 1] dp[i - 1][j]; } dp.push_back(row); } return dp; }这里有个小技巧用[1] * (i 1)初始化比显式给row[0]和row[i]单独赋值更简洁也不容易漏写边界。读代码的人一眼就能看出“首尾为1”这个条件被放在了初始化里而不是写在循环里。2.2 复杂度与边界条件分析二维dp版本的时间复杂度是 O(n²)因为你需要填满整个三角形总元素个数是12...n n(n1)/2。空间复杂度同样是 O(n²)因为你把每一行都保存了下来。对于 leetcode 这种判题环境n一般不超过 30 甚至更小所以这个复杂度完全没问题。但有几个边界条件必须想清楚numRows 0返回空列表。numRows 1只有一行[[1]]循环里的内层for j in range(1, i)不会执行直接返回即可。下标i从0开始还是从1开始我习惯从0开始这样dp[i]有i1个元素代码里所有地方都统一不容易混。有的题解从1开始那么第i行有i个元素转移方程变成dp[i][j] dp[i-1][j-1] dp[i-1][j]本质上没有区别但一定要保持整套代码下标一致。这些边界问题在力扣上其实不会太为难你因为题目给的测试用例通常都有正确的预期输出。但如果你在自己本地练习或者用在其他编程题平台上很容易因为n0返回了[[]]而报错。3. 空间优化倒推法一维数组一次AC的正确姿势3.1 为什么正着更新会覆盖数据二维dp虽然直观但很多刷题平台为了加大难度会要求你只输出杨辉三角的某一行而不是整个三角形。LeetCode 119题就是“杨辉三角 II”要求返回第rowIndex行从0开始。比如输入3输出[1,3,3,1]。这时候如果你还硬套二维dp空间复杂度 O(n²) 虽然也能过但面试官往往会追问“能不能只用 O(n) 的空间”答案是肯定的用一维数组滚动更新即可。但坑就在这里如果你直接正着遍历更新同一个数组会发现数据被覆盖了。举个例子你想把[1, 2, 1]更新成[1, 3, 3, 1]即从第2行推到第3行。用一维数组row初始为[1, 2, 1]然后想计算新一行的第2个位置下标1它等于旧行的row[0] row[1] 123你写入row[1] 3此时数组变成[1, 3, 1]。接着计算新一行的第3个位置下标2它应该等于旧行的row[1] row[2] 213但此时row[1]已经被覆盖成3了算出来就是314结果完全错误。你需要的其实是“上一行索引1位置的值”而这个值已经被当前行覆盖了。这就是正着更新会导致数据污染的根本原因。3.2 一维滚动数组代码与推导解决方式很简单从后往前更新。每次用这个位置原来的值也就是上一行的值和它前一个位置的值相加因为后一个位置的值在计算前还没被覆盖。下面是 LeetCode 119 的 Python 实现def getRow(rowIndex: int): row [1] * (rowIndex 1) for i in range(2, rowIndex 1): # i表示当前行号从第2行开始 # 从后往前更新避免覆盖 for j in range(i - 1, 0, -1): row[j] row[j - 1] row[j] return row我们手动走一遍rowIndex 3初始化row [1, 1, 1, 1]但注意这并不代表第3行的正确值我们只是用它作为暂存容器。i 2即第2行实际上要从第1行往上推但这里我们从第2行开始生成初始状态row全1相当于第1行。等等上面代码直接对[1,1,1,1]操作会得到什么更严谨的推导过程应该是def getRow(rowIndex: int): row [1] # 第0行 for i in range(1, rowIndex 1): # 在末尾加一个1代表新一行的最右边界 row.append(1) # 从倒数第二个元素开始向左遍历更新中间值 for j in range(i - 1, 0, -1): row[j] row[j - 1] return row这样可以避免“初始化成全1”带来的困惑。流程是row [1]i1先append(1)得到[1, 1]内层循环range(0,0,-1)为空结果正确。i2append后[1, 1, 1]内层j1row[1] row[0]即112得到[1, 2, 1]。i3append后[1, 2, 1, 1]内层j2row[2] row[1]即123得到[1, 2, 3, 1]j1row[1] row[0]即213得到[1, 3, 3, 1]。正确。这个“从后往前更新”的倒推法本质上就是滚动数组的标准写法。它把空间复杂度降到了 O(n)而且非常优雅。很多DP空间优化题比如背包问题的一维版本用的也是这个思路——当你需要用到上一层的状态又不想开二维数组时就让循环方向“反过来”。4. 刷题中的坑与刷题心态别小看输出格式和判题逻辑4.1 常见错误点杨辉三角题看似简单但我在各个平台上见过不少翻车案例最常见的以下几类第一忽略输入行数边界。有的平台测试输入是3预期输出是一个三行的三角形。但有些题目给你的numRows可能为0、1甚至负数虽然力扣一般不会给负数但自己写工具函数时要注意。如果你没有处理numRows 0直接dp[0]会越界。第二列表索引错位。比如用for j in range(1, i1)然后row[j] dp[i-1][j] dp[i-1][j-1]当j i时dp[i-1][i]并不存在就会越界。正确做法是内层只遍历到i-1或者用row [0] * (i1)再单独处理边界。我建议用[1] * (i1)初始化直接从根上避开这个坑。第三输出格式问题。很多在线编程平台比如某些实训平台要求严格输出带空格的三角形题目描述里会给出“测试输入3预期输出1 / 1 1 / 1 2 1”这样的格式。这时候如果你只返回一个二维列表或者输出时少打空格就算逻辑全对也会被判错。力扣上的题目一般不用处理打印格式但如果你在做头歌、OJ这类平台一定要先看清楚输出格式是每行数字之间用空格分隔还是逗号分隔是左对齐还是金字塔居中。这里有一个通用的做法先把每行转成字符串再用 .join(map(str, row))连接后输出手动控制缩进。4.2 本地测试和力扣判题的差异本地调试杨辉三角时我习惯写一个辅助函数打印整个三角形def print_triangle(tri): for row in tri: print( .join(map(str, row)))这样输出1 1 1 1 2 1 1 3 3 1可以直观看到每一行对不对。力扣判题只看你返回的数据结构所以你在本地打印的内容不影响提交。但有些新手会把print直接写在generate函数里导致返回值为None提交后直接报错。记住凡是要返回值的题目不要在函数里print最终结果除非题目明确要求“输出”而不是“返回”。此外力扣的测试用例通常是多组如果你的函数内部修改了全局变量或者没有正确初始化第二次调用就会出错。杨辉三角这类题不太涉及全局状态但如果你用类内属性来缓存结果要注意不同测试用例之间会不会互相干扰。我见过有人写了一个类变量cache结果上一次测试的numRows5没清空下一次numRows3直接返回了5行的内容。5. 从杨辉三角到动态规划思想的地图这道题如何延伸5.1 组合数公式和DP解法的选择杨辉三角第n行第k个数本质上是组合数C(n, k)。如果你只要求某一行也可以直接用组合数公式逐个算C(n,0)1然后C(n,k) C(n,k-1) * (n-k1) // k。这样连数组都不用时间复杂度 O(n)空间 O(1)。那为什么还要学DP解法因为组合数公式只是杨辉三角这一道题的“捷径”而DP解法传递的是更通用的思想。很多题目没有组合数公式这种闭式解你只能靠状态转移一步步推。比如“三角形最小路径和”“不同路径”“最长公共子序列”它们本质上的递推关系都和杨辉三角类似——当前位置的结果来自上一层的两个方向。如果你理解不了dp[i][j]是怎么由dp[i-1][j-1]和dp[i-1][j]相加得到的那后面这些题你会更晕。所以我的建议是就算你会用组合数秒杀119题也要把二维dp和滚动数组的写法各写一遍。这就像学数学用公式算出答案和用定义推导前者快后者才是真正理解。5.2 延伸题目与状态定义思路从杨辉三角出发你可以按“递增难度”刷这么几条线线性DP线爬楼梯70题、打家劫舍198题、等差数列划分413题。它们的状态都是一维的转移方程往往只依赖前一个或前两个状态。二维DP线不同路径62题、最小路径和64题、编辑距离72题。它们的状态是二维的和杨辉三角一样需要处理边界位置通常是第一行和第一列。空间优化线把二维dp压缩成一维比如62题的不同路径代码里可以用一个数组滚动更新技巧和杨辉三角的倒推法一模一样。具体来说不同路径的状态转移方程是dp[i][j] dp[i-1][j] dp[i][j-1]左下和上方的来源正好对应杨辉三角里的“左上方右上方”只是坐标方向不同。当你做空间优化时同样是从后往前更新只不过杨辉三角是一维数组里从右往左而不同路径是从右往左或从下往上原理完全相通。还有一类“倒推法”的题目比如从终点往前算其实和杨辉三角的滚动数组有异曲同工之妙你更新当前状态时不能破坏之前还要用到的状态。理解了这个“为什么倒着遍历”以后遇到任何滚动数组优化都不会再慌。写在最后的一点体会我在刷题时常常对简单题不屑一顾但杨辉三角是个例外。它把DP最核心的“状态定义、转移方程、边界初始化、空间优化”全部浓缩在十几行代码里。我第三次重做这道题时才真正理解为什么很多大佬会把它排在动态规划专题的第一题。如果你现在刚接触DP我建议你亲手把118题和119题分别用二维数组、一维滚动数组、组合数公式各写一遍对比三者的时间和空间开销。这个过程会让你对“动态规划到底在做什么”产生肌肉记忆比一味刷难题有效得多。另外一个小技巧刷完这道题后不妨去把“不同路径”和“最小路径和”做一遍你会发现它们的代码结构和杨辉三角惊人地相似——这就是DP题的魅力看似千变万化核心思想却是同一套。