1. 从一道入门题说起为什么所有算法新手都绕不开杨辉三角洛谷P5732题目全称是【深基5.习7】杨辉三角属于洛谷深入基础系列第五章的练习题。这个系列是给刚学完语法、开始接触算法的人准备的题目本身不难但每道题都卡在一个重要的思维转折点上。杨辉三角这道题卡的正是从会写循环到会用递推的那道门槛。很多刚刷题的同学看到这题第一反应是这不是小学奥数吗然后随手写个组合数公式套进去交上去结果不是超时就是溢出一片。也有人试图找规律直接输出折腾半天不如老老实实开数组模拟来得干净。这个现象其实挺有意思说明大家对杨辉三角的理解大多停留在知道长什么样的层面对它的构造逻辑反而没认真想过。这道题适合谁两类人。第一类是刚接触算法竞赛、准备系统刷洛谷入门题的新手需要通过简单题目建立递推状态的直觉第二类是学了一段时间但总觉得自己对二维数组、边界处理、输出格式这些基础功不扎实的人。你说这题难吗真不难但要把细节做到全对、思路理清楚里面还是有几个值得掰开揉碎讲的东西。我当年自己刷到这题的时候其实已经会做01背包那种题了但回头看P5732才发现杨辉三角在二维递推和组合数学里的位置远比想象中重要。它不只让你学会填表更重要的是让你第一次意识到一个看起来复杂的结果可以由前两个状态简单相加得到——这个思想往后会反复出现在DP、组合计数、概率论里。所以这篇就顺着这道题把杨辉三角的编程思路、边界细节、常见误区和延伸方向一次说透。另外多说一句洛谷的在线评测系统对输出格式要求很严格多了空格、少了换行都会判WA所以这题也是练格式化输出的好机会。很多人在算法上没错挂在格式上这种教训越早吃越好。2. 题干背面的数学本质递推关系与边界条件题目要求很简单输入一个整数n输出n行杨辉三角。样例输入5输出如下——1 1 1 1 2 1 1 3 3 1 1 4 6 4 1这个三角形每一个数等于它左上方和右上方的两个数之和。如果用坐标来理解假设行从1开始列从1开始那么第i行第j列的数a[i][j]满足a[i][j] a[i-1][j-1] a[i-1][j]其中每行的第一个数和最后一个数都是1也就是当j1或ji时a[i][j]1。2.1 为什么左上加右上等价于上一行两个数相加很多人第一次看到每个数是两肩之和这句话会懵图形上明明是一个数肩上扛着两个数怎么到代码里就变成上一行某两个位置相加了这里的关键是把斜着的三角形看成一个规整的二维矩阵。我们把第1行写入数组的第一行第2行写入第二行每一行的数字从第1列开始依次排开。这样一来第i行第j列的左上肩其实是上一行同一列的数a[i-1][j]因为上一行比当前行短一格上一行的第j个数恰好落在左上方右上肩则是上一行第j-1列的数a[i-1][j-1]。画个图就很清楚第i-1行: [a] [b] [c] 第i行: [ ] [x] [ ]x的左上方是上一行的a同一列右上方是上一行的b前一列所以x a b即x a[i-1][j-1] a[i-1][j]。这个等价关系一旦想通整个代码结构就明确了。2.2 边界条件的推导逻辑每一行的第一个数是1这对应j1的情况。但为什么最后一个数也是1原因在于按照递推公式自然算出来的结果就是1。比如第4行第4列的位置套公式需要上一行的第3列和第4列而上一行只有3个数第4列是0于是0加第3列的数1结果就是1。这里有一个很有意思的点如果数组是全局变量初始值全为0那么不特判ji也能算对最后一个数——它自动由上一行末尾的数加上0得到。但如果你把数组定义成局部变量不初始化里面的值是随机的这个加0的假设就不成立了输出可能爆炸。这个问题后面调试部分会细说。2.3 与组合数的关系杨辉三角第i行第j列的数其实等于组合数C(i-1, j-1)。这是杨辉三角和组合数学最核心的联系。用推导式算组合数是另一种解法但在这个题里我不推荐原因后面单独开一节讲。现在先记结论杨辉三角是组合数与递推之间的桥梁第n行所有数加起来等于2的n-1次方这也是一个可以用代码验证的有趣性质。3. 从公式到代码二维数组模拟的全过程有了递推公式和边界条件写代码就水到渠成了。下面给一个最标准、最适合入门的C版本然后逐步拆解每一步在干什么。#include iostream using namespace std; int a[25][25]; // 全局数组默认全部初始化为0 int main() { int n; cin n; for (int i 1; i n; i) { a[i][1] 1; // 每一行第一个数都是1 for (int j 2; j i; j) { a[i][j] a[i-1][j-1] a[i-1][j]; // 左上 右上 } } for (int i 1; i n; i) { for (int j 1; j i; j) { cout a[i][j] ; } cout endl; } return 0; }3.1 数组开多大才够题目一般没有明说n的最大值但按照深基系列的一贯风格n不会太大。代码里开25×25是为了保险实际n通常在10以内。如果要严谨一点可以先看题目的数据范围——n ≤ 10的情况开15×15就够如果不确定开大点总没错全局数组也不占多少内存。我见过有人把数组开成25×25却从0下标开始用最后各种越界和错位。这里统一从1开始存好处有两个一是行号列号与题目描述天然对应思维负担小二是j-1在j1时等于0正好落在全0的边界列不会访问到未定义区域。3.2 逐行填表的执行过程手算一遍n5的填表过程能帮你彻底理解递推是怎么滚动的i1先设a[1][1]1内层循环j从2到1不执行第一行填完。i2a[2][1]1j2时a[2][2] a[1][1] a[1][2] 1 0 1。i3a[3][1]1j2时a[3][2] a[2][1] a[2][2] 112j3时a[3][3] a[2][2] a[2][3] 101。i4依次得到1、3、3、1。i5依次得到1、4、6、4、1。注意每一步都用到了上一行已经算好的值这叫无后效性——当前状态只依赖之前的状态不依赖未来这正是递推能被循环实现的前提。3.3 关于内层循环从2开始的习惯为什么j从2开始而不是从1因为j1的情况已经单独赋值了。如果内层从1开始j1时会把a[i][1]重新计算成a[i-1][0] a[i-1][1] 0 1 1结果没错但多了一次无意义的运算而且读代码的人容易懵。从2开始是更清晰的习惯。还有一种做法是用if判断当j1或ji时赋1其他情况走递推。两种写法结果一样但先设边界再填内部的结构更接近初始化递推的思维模型后面学DP时你会发现几乎所有DP问题都是这个套路先初始化边界再填状态转移方程。现在养成这个习惯后面受益无穷。4. 易错点深挖为什么组合数公式在这道题里是陷阱看到杨辉三角很多数学直觉强的人会直接想到组合数公式C(n, k) n! / (k! * (n-k)!)心想我直接用公式算每一行不就行了何必要开二维数组递推这个思路本身没错但在算法题里埋着三个雷。4.1 雷点一阶乘溢出先看直观的写法long long factorial(int x) { long long res 1; for (int i 2; i x; i) res * i; return res; } long long C(int n, int k) { return factorial(n) / (factorial(k) * factorial(n - k)); }这个写法在n很小时没毛病但如果n到2020!已经超过unsigned long long的范围直接溢出。就算用杨辉三角递推第20行的数也才C(19,9)92378远没有溢出风险。换句话说杨辉三角用递推是边算边控制范围组合数公式是先把巨大的中间量算出来再除这两者的数值稳定性完全不同。可能有人说题目n不大我用long long也够啊。但你注意深基系列后面的题目数据范围会逐渐变大如果你不趁现在建立中间量溢出的意识后面遇到求C(100,50)的题目时大概率会踩同样的坑。4.2 雷点二重复计算的效率问题即使不考虑溢出用组合数公式算整张表每个数都要调用三次阶乘函数总共需要O(n^3)的时间。而递推每个数只做一次加法总时间是O(n^2)。题目要求n最多10的时候这个差距不明显但这道题的本质是教递推你要是用组合数公式通过就失去了练习的意义。别让题目过了思维还停在原地。4.3 雷点三模运算场景下公式失效很多后续题目会要求结果对某个质数取模比如对1000000007取模。这时候组合数公式里的除法不能直接做需要求逆元而递推加法完全不受影响模加还是加法。如果现在用公式后面遇到求杨辉三角第n行模p的题还得回头补逆元知识不如一开始就用递推把一个通用解法学会。4.4 什么时候才该用组合数公式不是一棒子打死。如果只求某个单点的组合数而不是生成整个三角形用公式或者卢卡斯定理更合理但生成整张表、且后续要做加法递推的场景二维数组递推永远是最稳的。这个选择题本身比题目答案更有价值——算法竞赛里选对方法往往比会写代码更决定命运。5. 输出格式的隐藏扣分点与调试心得洛谷对输出的判定是全文比对多一个空格、少一个空格都会WA。这道题的输出格式其实很宽松每行之间有换行每行的数字之间用空格分隔行尾可以有空格也可以没有因为OJ判这类题通常忽略行尾空格不对要小心洛谷的SPJ虽然有但这个题用的是非特殊裁判行尾空格一般会被接受但换行不能丢。从稳妥角度我建议养成一个好习惯每行数字之间用空格行末不要留多余空格输出完一行就换行。具体的做法是把输出空格和输出数字分开处理。我上面给的代码是直接在每个数后面加空格行末带一个空格也能过这是实测过的。但还是建议试试更严谨的写法for (int i 1; i n; i) { for (int j 1; j i; j) { if (j 1) cout ; cout a[i][j]; } cout endl; }这种方式的好处是第一个数前没有多余空格后续每个数前刚好一个空格格式最干净也符合人类阅读习惯。虽然洛谷这题不管行尾空格但万一以后遇到对空格敏感的题目这个习惯就直接用上了。5.1 用样例输出验证时的一个反直觉细节有人会在本地运行时发现第5行输出1 4 6 4 1后光标后面多了一个空格于是担心OJ会判错。其实大多数OJ对行尾空格是宽容的不会因为这个WA所以不用为了这点强迫症去改代码。真正要关注的是该有换行的地方有没有换行——如果你把endl写在数字循环外面但忘了那就会所有数字挤成一团这必WA。调试时还有个小技巧把屏幕输出重定向到文件再用diff命令对比样例能迅速定位格式问题。Windows下用fcLinux下用diff。我第一次刷洛谷时就因为行尾空格纠结了半天后来发现根本不影响真正错的是数组边界没处理好导致最后一行多出了个0。5.2 一段能复现的错误输出经历拿最初版代码如果把数组定义在main函数里且不初始化然后写循环填表内层循环j从1到i每一格都用a[i-1][j-1] a[i-1][j]算你大概率会看到输出里出现随机大数。原因是局部数组的初始值是栈里的残留数据不是0。递推公式依赖超出区域的值是0这个前提前提一破整个表全错。我自己第一次写这道题时就是这样WaWrong Answer了两发才反应过来。后来养成一个习惯算法题里需要默认周围是0的数组一律放全局或者用memset/vector初始化清零。全局变量自动初始化为0这条C规则是无数刷题人用WA换来的教训。5.3 关于洛谷评测的内存与时间看懂数据范围P5732的n范围非常小所以内存和时间完全不是瓶颈。但这道题的意义在于让你习惯一个流程先看数据范围再决定数组大小和算法。我见到不少人是先写代码再补数组结果开了个10×10的数组n一超过10就越界崩掉。正确顺序永远是n能有多大数组开多大多留一点余量。6. 从P5732延伸开去这道题连接着哪些更高阶的内容杨辉三角就像一个中转站往左是递推、往右是组合数、往上是一维数组优化、往下是DP。这一节聊聊从这道题出发可以往哪些方向深入给刷题路线指个方向。6.1 一维数组滚动优化如果不需要保留整个三角形只需要输出当前行可以用一个一维数组反复覆盖。核心代码是内层循环从后往前更新for (int j i; j 1; j--) { a[j] j 1 ? 1 : a[j] a[j-1]; }为什么要从后往前因为如果从前往后a[j]的新值会覆盖旧值而计算a[j1]时需要的恰好是旧的a[j]——被覆盖了就全乱了。从后往前更新保证每个位置用它左边还没有被更新的旧值。这个滚动数组逆序更新的技巧后面在背包问题的优化里几乎天天用值得现在就练。6.2 二项式系数与帕斯卡恒等式杨辉三角第n行的数就是(x y)的n次方展开式的系数这个联系在多项式、概率、矩阵快速幂里都有应用。帕斯卡恒等式C(n, k) C(n-1, k-1) C(n-1, k)就是递推公式的数学表达。如果你以后学生成函数会发现杨辉三角只是更宏大理论的冰山一角。打个比方杨辉三角就像线性代数里的单位矩阵——单独看没什么稀奇但它是无数复杂操作的基石。你越往后刷题越会发现这个三角形的影子出现在筛法、卡特兰数、动态规划的路径计数里。6.3 路径计数模型的雏形有一个经典的DP入门题叫从网格左上角走到右下角有多少种走法它的状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]和杨辉三角的递推几乎一模一样。区别只是杨辉三角是上一行的两个位置相加网格是左边和上边的两个位置相加。两者背后的逻辑都是到达当前位置的方法数等于能走到它的所有来源之和。这个思想是DP最原始的形式。很多新手一开始理解不了DP的状态转移是什么意思但如果你先把杨辉三角的填表过程玩明白再看路径计数会发现一切都很自然。所以说P5732不只是简单输出一个三角形它是你第一次亲手搭建一个状态表。6.4 卡特兰数的影子杨辉三角中间那一列第2n行第n列可以组合出卡特兰数卡特兰数又出现在括号匹配、出栈序列、二叉树计数等经典问题里。路径是先学递推基础再学到卡特兰数时回头看看杨辉三角会有一种原来当初学的都是伏笔的感觉。7. 一些我在实际刷题中总结的细节习惯讲完原理和代码最后抖点实际操作层面的心得。这些写在教材里往往被忽略但对入门者来说恰恰很管用。第一刷题时尽量用全局数组。不只是这个题后面很多二维DP题都依赖数组默认清0的便利。局部数组一旦忘了初始化WA到怀疑人生还很难查。如果一定要在局部用直接写成int a[25][25] {}; 强制清零比写memset更省事也避免记错memset按字节赋值的坑。第二提交之前先在本地用边界数据测一下。这个题至少测一次n1输出应该是单独一行1再测n2确保第二行是1 1。很多WA都是小数据对了、大一点就边界出问题从小数据想起能快速定位。不要只测题目给的样例就急着交样例过了只能说明样例没问题。第三理解为什么代码长这样比抄代码重要。如果你能把a[i][j] a[i-1][j-1] a[i-1][j]这个式子跟每个数是左上方和右上方两个数之和互相翻译说明你真的懂了。如果做不到试着在纸上画出数组下标和三角形形状的对应关系这个对应关系想通了这题就真通了。第四关于时间复杂度的一个小直觉O(n^2)和O(n^3)在数据量小的时候没区别但刷题是为了应对未来更大的数据。养成每次思考都附带计算复杂度的习惯比多刷二十道简单题都值。P5732里的递推是O(n^2)最优解法任何一个用组合数公式循环计算的写法都是O(n^3)——这本身就是知识点。第五也是我认为最重要的一条做完题之后花五分钟想想这题如果改成输出第100行的某个数我该怎么做如果把n放大到1000、100000递推还成立吗内存还够吗要不要用模运算这些延伸问题才是刷题真正增值的地方。P5732本身很简单但它背后钩着的那些问题每一个都值得你多琢磨一会儿。