每次刷算法题都能看到杨辉三角从 LeetCode 到各种实验平台它就像算法题里的 Hello World但真正能把这道题吃透的人其实不多。最近我在一个在线练习平台看到一道用倒推法求杨辉三角并输出的任务输入总行数 3预期输出一个居中的数字三角形看起来不难真动手写才发现这里面的门道比想象中多——递推关系怎么定、边界怎么处理、输出空格怎么对齐每一个细节都会影响你能不能一次通过测试。这篇文章就以每天学习一点算法的节奏把杨辉三角这道题从头拆到尾包括数学本质、倒推法递推/动态规划的思路、Python 和 C 语言的实现、滚动数组优化、输出格式控制以及我实际做题时踩过的坑希望能给正在刷算法入门题的朋友一点帮助。1. 一道看起来简单的杨辉三角为什么值得单独写一篇1.1 从一次笔试/实验任务说起那天我看到的题目描述是这样的在右侧编辑器 begin-end 处补充代码完成本关任务。测试输入是 3也就是杨辉三角的总行数预期输出是1 1 1 1 2 1当时第一反应是这不就是两层循环套一下的事吗结果写出来一跑先挂在了边界条件上——第二行和第三行的中间数字没有正确累加紧接着又挂在输出格式上——空格数量不对整个三角形是歪的。那一刻我才意识到这道题之所以被放在各种算法课程的入门关不是因为代码量大而是因为它把递推和输出控制这两个基本功捏在了一起。从算法学习的角度看杨辉三角几乎涵盖了入门阶段最重要的几个关键词组合数、递推关系、动态规划雏形、时间复杂度分析、空间优化。把这题真正搞懂后面再看数字三角形、爬楼梯、不同路径这些经典题会顺很多。1.2 杨辉三角的数学本质先回到定义本身。杨辉三角也叫帕斯卡三角在中国历史上更早可以追溯到贾宪和杨辉的记载。它的构造规则极其简单每行第一个和最后一个数字是 1中间每个数字等于它正上方和左上方两个数字之和。如果用行号和列号来表示第i行从 0 开始第j列的数字a[i][j]满足a[i][0] 1 a[i][i] 1 a[i][j] a[i-1][j-1] a[i-1][j] (1 j i-1)这个递推关系本身就是算法里的状态转移方程。数学上a[i][j]正好等于组合数C(i, j)也就是二项式(a b)^i展开后第j1项的系数。比如(a b)^4 a^4 4a^3b 6a^2b^2 4ab^3 b^4系数是1 4 6 4 1刚好是杨辉三角第 5 行的数字。也正因为这个性质杨辉三角不是一道孤立的打印题。它在概率论的二项分布、排列组合的计算、甚至某些机器学习模型的组合特征构造里都会冒出来。刷题的时候把它当成数学规律 代码实现的结合体来看收获会大得多。1.3 隐藏的考点如果只是要求输出数字不考虑对齐这道题确实简单。但大多数评测系统不会只比对数字序列而是直接比对完整文本包括空格和换行。这就带来了第二个隐藏考点格式化输出。我在不少交流群里看到有人问为什么我算对了但测试不通过九成都是空格问题。有的题目要求每个数字之间固定两个空格有的要求按等宽字符居中有的要求行末不能有多余空格而这些差异只有仔细读题才能发现。所以在做这道题时我建议把它拆成两个阶段先确保递推结果正确再专门处理输出格式两件事分开调试出问题的时候才不会一头雾水。2. 倒推法到底是怎么一回事递推、DP与状态转移2.1 倒推法的核心思想题目里提到的倒推法在不同教材里叫法不太一样有的叫递推法有的直接叫动态规划。它们的共同点是当前结果依赖前面已经算好的结果只能从最小的问题开始一层一层往后推。拿杨辉三角来说你想直接算出第 5 行第 3 个数是多少不看前面几行是做不到的。因为它定义上就依赖第 4 行第 2 个数和第 4 行第 3 个数而这两个数又依赖第 3 行……这样一路回溯到第一行的那个 1。倒推法做的就是把这个依赖顺序反过来从第一行开始把每一行都算出来并保存后面行直接取用。举一个生活化的例子。你要统计一个班每一排的人数如果直接看最后一排你数不清因为前面几排有人站着有人坐着挡住了视线。正确做法是从第一排开始一排一排数过来数到哪一排就用前一排的累计结果加上当前排新增的人数。杨辉三角同理从左上到右下逐行推进就是最自然的倒推。2.2 状态定义和转移方程用算法的话说我们先定义状态dp[i][j]表示第i行第j列的值。然后写状态转移方程dp[i][j] dp[i-1][j-1] dp[i-1][j]这个方程的约束很关键j既不能等于 0 也不能等于i因为这两个位置是边界没有左上或正上方的数可用。如果你在代码里不先判断边界就直接访问dp[i-1][j-1]或dp[i-1][j]轻则结果错误重则数组越界崩溃。所以完整的生成逻辑是输入总行数n从第 0 行到第n-1行逐行处理每行的首尾都直接置 1中间位置用转移方程计算输出或继续下一行。这个流程是典型的自底向上动态规划。虽然没有复杂的最优解问题但 DP 的两个核心特征它都具备重叠子问题同一个dp[i-1][j]会被下一行的两个位置重复使用和递推关系当前状态由前一状态推出。你把这个流程吃透后面学背包、区间 DP 时会觉得思路特别顺。2.3 边界与初始化很多新手写这类题目第一个 bug 出在行数从 0 开始还是从 1 开始。数学上习惯从第 1 行开始但代码里数组下标是 0 开始的。我建议统一用 0 基下标循环范围是i 0; i n; i这样dp[i][0] 1、dp[i][i] 1的边界写起来最直观。另一个容易犯的错是忘记初始化。如果语言里数组默认不是 0比如某些环境下声明后是随机值而你只给部分位置赋值后面按dp[i-1][j-1] dp[i-1][j]计算时会用到垃圾值。稳妥的做法是显式初始化整块数组为 0再把对角线首尾覆盖为 1。提示判断一个递推实现是否正确的快速方法是手动在纸上写出前 4 行然后和代码输出对比。如果1 1、1 2 1、1 3 3 1没问题基本就对了。刷算法题最忌讳直接跑大数据集调试因为输出一多你根本看不清错在哪一行。3. 三种主流实现Python、C语言和滚动数组3.1 Python最贴近思维的写法Python 写杨辉三角可以非常直接。既然每行的长度是递增的我们可以用一个二维列表把所有行保存下来def generate_pascal(n): triangle [] for i in range(n): row [1] * (i 1) for j in range(1, i): row[j] triangle[i - 1][j - 1] triangle[i - 1][j] triangle.append(row) return triangle if __name__ __main__: n int(input().strip()) for row in generate_pascal(n): print(row)这段代码里有两个细节值得说。第一row [1] * (i 1)一次性把整行先填成 1这样首尾就天然满足边界条件中间再覆盖。第二内层循环range(1, i)只处理j 1到i-1也就是跳过首尾避免越界访问。如果题目只需要逐行输出、不要求保留全部历史值甚至可以不建二维数组row [1] for i in range(n): print( .join(map(str, row))) next_row [1] for j in range(len(row) - 1): next_row.append(row[j] row[j 1]) next_row.append(1) row next_row这里我觉得最值得品的是next_row的构造方式它由上一行相邻两数相加得到。从算法角度讲这保留了递推的本质同时省去了用索引访问二维数组的麻烦。Python 的表达力在这种小问题上体现得淋漓尽致。3.2 C语言常见OJ环境的注意点很多学校的实验平台、OJ 系统用的是 C 语言代码风格偏严谨。一个典型实现是#include stdio.h #define MAXN 100 int main() { int n; scanf(%d, n); int a[MAXN][MAXN] {0}; for (int i 0; i n; i) { a[i][0] 1; a[i][i] 1; for (int j 1; j i; j) { a[i][j] a[i-1][j-1] a[i-1][j]; } } for (int i 0; i n; i) { for (int j 0; j i; j) { printf(%d , a[i][j]); } printf(\n); } return 0; }用 C 写时有三个坑是新手几乎必踩的数组开多大MAXN要根据题目给的行数上限设置开小了越界开太大在栈上浪费内存。有的 OJ 题目n可能到 1000二维1000 x 1000的int数组大约 4MB栈上默认不一定够可以考虑声明成static或全局变量。scanf之后没有检查返回值。虽然简单题不会考这个但养成if (scanf(%d, n) ! 1) return 0;的习惯在复杂题目里能帮你避免不少玄学错误。输出时每个数字后面统一跟一个空格行末会多一个空格。某些严格的 OJ 会因此判 Presentation Error格式错误所以如果题目明确要求行末不能有空格要单独写分支。3.3 滚动数组把空间从 O(n^2) 降到 O(n)刷题刷多了你会发现很多题目不要求保留所有中间结果只要求最终输出。这时可以只维护上一行和当前行两个一维数组甚至只用一个数组原地更新。原地更新的核心是从后往前遍历def print_pascal_compact(n): row [1] for i in range(n): print( .join(map(str, row))) # 从后往前更新避免覆盖尚未使用的旧值 for j in range(len(row) - 1, 0, -1): row[j] row[j - 1] row[j] row.append(1)为什么必须从后往前用一个例子解释假设当前row [1, 2, 1]你想生成下一行[1, 3, 3, 1]。如果从左往右更新先算row[1] row[0] row[1] 3此时原来的row[1] 2被覆盖了再算row[2] row[1] row[2]时拿到的是新的3而不是原来的2结果变成4彻底算错。从右往左算时row[2]用的是还没被改动的row[1]和row[2]安全。这个技巧在动态规划的很多题目里都会用到比如背包问题的空间优化。提前在杨辉三角上练会后面遇到只保留上一行状态的场景会非常自然。4. 输出格式专门谈一谈4.1 预期输出的空格与对齐回到题目预期的输出1 1 1 1 2 1看起来是一个按空格居中的三角形。这种格式在控制台里好看但在 OJ 的文本比较里非常危险因为空格数量的细微差异可能导致误判。所以先搞清楚评测系统到底在比对什么。一部分平台只比对数字序列的位置是否相同空格数量和换行可以宽松处理另一部分平台是全文本严格匹配。从只有所有数据全部计算正确才能通过测试这句描述来看这道题大概率会同时校验结构和数值所以输出格式不能随意。我的建议是不要猜先用一个标准输出看评测反馈。先按最普通的数字 空格 换行输出提交一次看错误提示再根据反馈调整如果题目明确给了带格式的预期输出就严格按那个格式生成。4.2 格式化输出的几种写法如果要在终端里打印一个居中的金字塔最省事的方法是给每个数字分配固定宽度数字本身左对齐、右对齐或居中。C 语言里可以用%4d这种格式for (int i 0; i n; i) { for (int j 0; j n - i - 1; j) { printf( ); // 三个空格凑一个数字宽度 } for (int j 0; j i; j) { printf(%3d , a[i][j]); } printf(\n); }Python 里可以用字符串格式化def print_triangle(n, triangle): width len(str(triangle[-1][-1])) 2 # 以最大数字宽度为基准 for i, row in enumerate(triangle): left_space * (width * (n - i - 1) // 1) print(left_space .join(f{num:^{width}} for num in row))这里我特别提醒一点不要为了追求美观而让每个数字占不等宽的格子。比如数字有 1 位、2 位、3 位混在一起中间间距会看起来忽宽忽窄。固定宽度格式化可以保证所有行在视觉上严格对齐也更容易满足评测规则。4.3 行末空格和换行这是我实际做题时踩过的一个坑。很多平台的输出比对逐字符进行如果题目说每个数字之间用一个空格分隔那行末通常不应该有空格。但有的模板代码直接写printf(%d , a[i][j])每行最后多了一个空格照样能过因为平台把行末空格忽略了。不同平台标准不一最稳妥的做法是让每行最后一个数字后面不跟空格for j in range(i 1): if j 0: print( * indent, end) if j i: print(row[j]) # 行末不加多余空格 else: print(row[j], end )这种写法代码稍长但兼容性最好。如果你在实验中提交后提示Presentation Error或格式错误九成就是行末空格或换行符的问题不用改算法只改输出逻辑。5. 复杂度分析和一道题的联想空间5.1 时间复杂度和空间复杂度怎么算理解了递推关系复杂度其实很好推导。如果用一个n x n的二维数组保存整个杨辉三角那么每个位置(i, j)计算一次内层是常数时间加法总操作次数约等于三角形内的元素个数也就是n(n1)/2时间复杂度就是O(n^2)空间复杂度是O(n^2)因为存储了全部行。如果用滚动数组只保留上一行空间复杂度可以降到O(n)时间仍然是O(n^2)因为每个位置的加法省不掉。有些同学会问能不能用组合数公式直接算出第n行的第j个数从而把复杂度降到O(n)理论上可以用组合数的递推式C(n, j) C(n, j-1) * (n - j 1) / j但这里有个精度和整除的坑。如果直接用浮点数运算n稍大就会出现精度误差如果用整数按先乘后除的顺序又可能出现中间结果溢出。所以在入门阶段我不太建议靠组合数公式去做这道题老老实实递推最可靠。等学到大数处理或者模运算时再回来用组合数优化也不迟。5.2 从杨辉三角到其他经典题目杨辉三角的递推模式在很多算法题里都能看到影子数字三角形给一个三角形从顶部走到底部求路径和最大。它的状态转移是dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) triangle[i][j]跟杨辉三角的转移方向几乎一样只是把加法换成了取最大值。爬楼梯到达第n级台阶的走法数满足dp[n] dp[n-1] dp[n-2]本质也是递推。不同路径机器人从网格左上角走到右下角状态转移是dp[i][j] dp[i-1][j] dp[i][j-1]这其实就是杨辉三角的二维推广所以方格里填出来的数字就是组合数C(ij, i)。二项分布概率论里n次独立实验成功k次的概率包含组合数C(n, k)这些系数构成的曲线就是二项分布而二项分布的形状本身就长在杨辉三角的某一行里。你把杨辉三角的递推练熟了再遇到这些题会明显感觉似曾相识。这也是为什么很多刷题攻略把杨辉三角列在动态规划入门的第一个推荐题。5.3 组合数公式与数学视角的补充前面提到杨辉三角第n行第k个数等于C(n, k)这给了一个非常强的自检手段你写完代码后可以把某一行输出和组合数公式计算的结果对照。比如第 6 行应该是1 5 10 10 5 1C(6,2) 15等等。如果对不上直接定位是哪一列算错了。另一个有趣的数学性质是行和第n行的所有数字之和等于2^n。比如第 3 行1 3 3 1的和是 8。这个性质也可以用来验证实现的正确性在测试时如果输出和2^n不符说明中间某些位置算错了。这些数学规律不是考试必须的内容但能帮你建立对算法和数学如何互相验证的直觉。以后处理更复杂的数据结构问题时你会习惯性地从数学角度去找规律而不是死记代码。6. 我的学习建议和踩坑记录6.1 动手前先手推别一上来就写代码。我自己的习惯是先在纸上画 5 行杨辉三角把每一行的数字来源用箭头标出来。比如第4行第2个数字3 第3行第1个数字1 第3行第2个数字2。这个步骤看起来简单但对建立递推直觉特别重要尤其是刚开始学算法的朋友跳过这一步直接写代码很容易陷入照着模板改但不理解的状态。手推一遍之后再写代码你会发现所谓的状态转移方程其实就是你在纸上反复画的那个箭头关系。这时候再去看那些动态规划的复杂题目至少不会觉得状态转移方程是个从天而降的公式。6.2 常见错误排查表我把自己和身边同学在杨辉三角这道题上踩过的坑整理成了一张表刷题时可以直接对照排查错误类型现象原因解决办法越界访问程序崩溃或输出乱码内层循环没有跳过首尾位置用j 1; j i; j限制范围覆盖旧值中间数字偏大一维数组从左往右原地更新改为从后往前更新数组未初始化结果不稳定声明的静态数组里残留脏数据显式初始化为 0行末空格提示格式错误输出时每个数字都跟了空格最后一个数字单独处理输入读取失败卡在等待输入scanf/input格式不匹配先确认测试输入格式这些错误在其他数组和动态规划题里同样常见早点遇到反而是好事至少知道出问题了该往哪里排查。6.3 后续可以怎么继续学如果你把杨辉三角彻底搞明白了我建议按这个顺序继续往下走先把滚动数组练熟尝试给杨辉三角输出每一行时只保留上一行并且不借助额外二维数组。试着用动态规划的思路做数字三角形对比两者状态转移方程的差异。再试试 LeetCode 上杨辉三角 II它的要求是只返回某一行的结果必须用O(k)空间正好把滚动数组派上用场。学有余力的话把组合数的取模运算也加进来比如输出C(n, k) mod 1000000007这会让你接触到模运算和数据溢出处理是算法竞赛里非常常见的技巧。我个人在实际做题时感触最深的一点是杨辉三角这道题真正难的从来不是打印数字而是你能不能把它抽象成递推关系 边界处理 格式化输出这三个独立问题。分而治之逐个解决一道入门题也能成为后面所有动态规划题的基石。每天花十几分钟把这类经典题吃透比一天刷十道题然后全部忘光要划算得多。