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，也就是：当j=1或j=i时，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，这对应j=1的情况。但为什么最后一个数也是1？原因在于，按照递推公式自然算出来的结果就是1。比如第4行，第4列的位置，套公式需要上一行的第3列和第4列，而上一行只有3个数，第4列是0，于是0加第3列的数1，结果就是1。
这里有一个很有意思的点：如果数组是全局变量，初始值全为0，那么不特判j=i也能算对最后一个数——它自动由上一行末尾的数加上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在j=1时等于0，正好落在全0的边界列，不会访问到未定义区域。
3.2 逐行填表的执行过程
手算一遍n=5的填表过程，能帮你彻底理解递推是怎么"滚动"的：
- i=1：先设a[1][1]=1，内层循环j从2到1不执行，第一行填完。
- i=2：a[2][1]=1，j=2时，a[2][2] = a[1][1] + a[1][2] = 1 + 0 = 1。
- i=3：a[3][1]=1，j=2时，a[3][2] = a[2][1] + a[2][2] = 1+1=2；j=3时，a[3][3] = a[2][2] + a[2][3] = 1+0=1。
- i=4：依次得到1、3、3、1。
- i=5：依次得到1、4、6、4、1。
注意每一步都用到了上一行已经算好的值，这叫"无后效性"——当前状态只依赖之前的状态，不依赖未来，这正是递推能被循环实现的前提。
3.3 关于"内层循环从2开始"的习惯
为什么j从2开始而不是从1？因为j=1的情况已经单独赋值了。如果内层从1开始，j=1时会把a[i][1]重新计算成a[i-1][0] + a[i-1][1] = 0 + 1 = 1，结果没错，但多了一次无意义的运算，而且读代码的人容易懵。从2开始是更清晰的习惯。
还有一种做法是用if判断，当j==1或j==i时赋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到20，20!已经超过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下用fc，Linux下用diff。我第一次刷洛谷时就因为行尾空格纠结了半天，后来发现根本不影响，真正错的是数组边界没处理好导致最后一行多出了个0。
5.2 一段能复现的"错误输出"经历
拿最初版代码，如果把数组定义在main函数里且不初始化，然后写循环填表，内层循环j从1到i，每一格都用a[i-1][j-1] + a[i-1][j]算，你大概率会看到输出里出现随机大数。原因是局部数组的初始值是栈里的残留数据，不是0。递推公式依赖"超出区域的值是0"这个前提，前提一破，整个表全错。
我自己第一次写这道题时就是这样，Wa（Wrong 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[j+1]时需要的恰好是"旧的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按字节赋值的坑。
第二，提交之前先在本地用边界数据测一下。这个题至少测一次n=1，输出应该是单独一行1；再测n=2，确保第二行是"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本身很简单，但它背后钩着的那些问题，每一个都值得你多琢磨一会儿。
