1. 杨辉三角形的数学骨架从一个看似“对称”的规律说起很多第一次接触杨辉三角形的人都会被它整齐的轴对称外观吸引每一行的两端都是1中间的数字恰好是上一行相邻两个数字之和。这个东西在中学数学里叫“二项式系数表”在组合数学里又和“C(n, k)”紧密挂钩在算法题里则是一个经典的“递推 输出格式控制”入门题目。刚开始刷算法题或者刚学Java数组的时候拿它练手非常合适——它简单到不需要任何第三方库但又足够让你把二维数组、循环嵌套、字符串格式化、甚至时间复杂度分析这些基础概念完整地串一遍。我在带某位刚开始学Java的朋友做这个题目时发现一个普遍现象大家在网上搜到的解法大多能跑出正确的数字但一旦把行数调到10以上输出就开始歪歪扭扭把行数改成0或者1程序又直接崩溃。这说明什么说明大多数实现只是“凑出了结果”并没有真正理解杨辉三角形背后的递推结构。这篇文章我不会只丢一段能跑通的代码而是把从数学原理到工程实现的完整链条拆开讲清楚包括为什么二维数组是初学者最直观的选择、什么时候该换成一维数组节省空间、空格对齐为什么是个“看着小但很影响体验”的问题以及哪些边界情况容易让你在面试或上机考试里翻车。先把这个三角形的递推关系用最直白的方式说明白如果把第n行第k列的值记为value[n][k]那么它满足三条规则——第一当k等于0或者k等于n的时候值恒为1也就是每行的首尾两个数字第二对于0 k n的情况value[n][k] value[n-1][k-1] value[n-1][k]第三所有其他位置的值默认为0不参与计算。这三条规则合在一起就是一个典型的“当前状态只依赖上一行状态”的动态规划雏形。你可能会问为什么首尾一定是1这得从组合数的角度理解。杨辉三角形的第n行恰好对应着(a b)^n展开后的各项系数首尾两项的系数必然是1因为那是“全选a”或“全选b”的唯一组合方式。而中间任何一个数字比如C(n, k)都满足C(n, k) C(n-1, k-1) C(n-1, k)这个恒等式就是杨辉三角形递推公式的数学来源。一旦你理解了这层关系写代码时就不会再去硬记公式而是自然地想到“从上一行抄两个数相加”。2. 动手写代码前的三个关键设计决策数组形状、循环边界和数据类型在打开IDE敲代码之前有三件事必须先在脑子里做出决定。第一用二维数组还是“看起来像二维”的列表第二循环的起止边界怎么定才能既不越界又不产生多余的空值第三数值类型用int还是long。这三件事决定了你的代码是“能跑”还是“跑得稳”。2.1 选二维数组的直觉理由以及一个更省内存的替代方案最直观的存储方式就是声明一个int[][]二维数组行数等于用户输入的行数列数也等于行数然后只填充“左下三角”区域。为什么列数要等于行数而不是动态变化原因只有一个Java的二维数组本质上是一维数组的数组你当然可以让每一行拥有不同的长度这种叫“不规则数组”但对于杨辉三角形这个场景统一长度带来的好处是下标计算更简单、内存分配的规律更清晰、打印时即使误读了未填写的元素也不会越界。坏处是浪费了大约一半的空间那些右上三角的位置永远都是默认的0。如果题目要求的行数特别大比如500行以上int[500][500]要占大约1MB的堆内存这时候就可以考虑用一维数组滚动更新。核心思路是既然每一行的值只依赖上一行那我只需要一个长度为n的一维数组row每一轮从后往前更新这个数组。为什么必须“从后往前”因为row[k] row[k-1] row[k]这个公式里等号右边的row[k-1]是上一轮即上一行的值如果从前往后更新row[k-1]已经被本次循环覆盖成新值了计算结果就全错了。从后往前更新则能保证用到的始终是旧值。这是一个经典的“滚动数组”技巧也是面试时展示你思路进阶的加分项。2.2 循环边界为什么外层到n、内层到i就正好确定了数组形状接下来最容易写错的就是循环边界。我见过很多次这种错误内层循环也写成了for (int j 0; j n; j)结果左下三角还没填完就把右上三角的默认0也读进来参与运算导致下一行出现一堆错误的数字。正确做法是外层循环for (int i 0; i n; i)代表当前行内层循环for (int j 0; j i; j)只处理本行从左到右的i1个有效位置。这里再强调一个关键判断j 0 || j i时必须直接赋值为1而j 0 j i时才执行加法。为什么j i也必须算作边界因为每行的最后一个数字就是对角线上的那个1。很多初学者只判断了j 0结果对角线上全变成了0漏掉了首尾为1的规则输出就变成了一个“缺角”的三角形。2.3 int足够吗聊聊大数溢出的边界问题第三个设计决策是数据类型。杨辉三角形的数值增长非常快第30行的中间值大约是300540195已经逼近int的最大值2147483647到第34行中间值就超过int范围了。如果你的程序允许用户输入较大的行数比如60行、80行那么用int就会得到一堆负数看起来就像程序“坏了”。我自己实测过第35行的中心值约为1166803110还没爆但第36行中心值约为601080390也还没爆真正开始爆是在第35行之后的某些位置开始陆续出现负数。稳妥起见如果只是做课程作业或面试题int在n ≤ 33时是安全的如果想让程序更健壮直接把数组声明成long[][]并且在输出时用System.out.print(row[j] )代价仅仅是内存翻倍。对于n ≤ 66的题目long也够用再往上就需要BigInteger了那就是另一个话题。3. 从零实现二维数组直推版与一维数组滚动版第2节讲清楚了设计决策这一步就纯粹是“实现逻辑”了。我给两个版本第一个版本适合入门理解第二个版本适合在空间受限或刷题时使用两者我都会给出完整的代码和逐行说明。3.1 版本一二维数组直推版import java.util.Scanner; public class YangHuiTriangleV1 { public static void main(String[] args) { Scanner scanner new Scanner(System.in); System.out.print(请输入杨辉三角形的行数: ); int n scanner.nextInt(); scanner.close(); int[][] triangle new int[n][n]; for (int i 0; i n; i) { for (int j 0; j i; j) { if (j 0 || j i) { triangle[i][j] 1; } else { triangle[i][j] triangle[i - 1][j - 1] triangle[i - 1][j]; } } } for (int i 0; i n; i) { for (int j 0; j i; j) { System.out.print(triangle[i][j] ); } System.out.println(); } } }这段代码的核心就两句话。填充时triangle[i][j]只依赖triangle[i-1][j-1]和triangle[i-1][j]而这两个值在上一轮外层循环中已经算好了所以不需要递归不需要额外判断“上一行是否存在”因为i从0开始当i1时i-10必然已经计算完毕。打印时同样使用j i的边界保证只打印有效数字而不是把整行的尾随0打出来。这里有个细节值得留意我用的是固定列数的方阵所以triangle[1][1]这种位置也存在但它在i1行的循环里会被填入1后续行的加法也会正确引用它。如果是“不规则数组”每一行的长度不同写法上就需要在创建时给每一行单独分配长度比如说triangle[i] new int[i 1]。两种写法的结果一样但固定列数版本更简洁适合教学。3.2 版本二一维数组滚动更新版import java.util.Scanner; public class YangHuiTriangleV2 { public static void main(String[] args) { Scanner scanner new Scanner(System.in); System.out.print(请输入杨辉三角形的行数: ); int n scanner.nextInt(); scanner.close(); long[] row new long[n]; for (int i 0; i n; i) { // 从后往前更新避免覆盖还没使用的左邻旧值 for (int j i; j 0; j--) { if (j 0 || j i) { row[j] 1L; } else { row[j] row[j - 1] row[j]; } } for (int j 0; j i; j) { System.out.print(row[j] ); } System.out.println(); } } }你可以把row想象成一条传送带第i轮结束后传送带上的第0到第i号位置就存放着第i行的所有数字。因为每一行都覆盖了上一行的数据所以空间占用从n * n降到了n。代码中唯一需要警惕的就是for (int j i; j 0; j--)这个倒序循环。举个例子当i2, j1时row[1] row[0] row[1]等号右边的row[0]是上一行位置0的值也就是1右边的row[1]也是上一行位置1的值上一行i1时的末尾数字1相加得到2这个2正确地写入了row[1]。如果改成从前往后循环j1时会先覆盖row[1]等到j2时虽然用的是row[1] row[2]但这里的row[1]已经是新值2而不是上一行的1结果就变成2 1 3整个数据链就污染了。这两个版本的输出完全一致你可以随意挑一个作为基础再继续加格式美化。4. 输出对齐真正“好看”的杨辉三角形长什么样不少教程到此就结束了会告诉你“打印结果如下”但实际跑出来你会看到第一行是1第二行是1 1第三行是1 2 1……全部左对齐挤在一起根本看不出三角形的形状。要做成一个“真正像三角形”的输出必须处理两件事每个数字占用的固定宽度以及每行开头的空格数。4.1 先算出最大数字的位数再决定每个数的打印宽度一个常见的做法是先找到整个三角形中最大的那个数也就是最后一行的中间值把它转成字符串取它的长度作为maxWidth。每个数打印时都补足到maxWidth 1或maxWidth 2的空格位。为什么加1或加2因为如果只取最大值的位数相邻数字之间没有额外间隔看起来仍然很挤加一个空格作为数字之间的分隔视觉上才舒服。int maxVal triangle[n - 1][n / 2]; // 最后一行中间的数通常是最大值 int maxWidth String.valueOf(maxVal).length();这里有个小坑n / 2是整数除法当n为奇数时比如n55 / 2 2对应第3列下标从0开始它确实是这行的最大值位置当n为偶数时比如n66 / 2 3对应第4列但这行的最大值可能出现在第3列或第4列两者相等所以取n / 2完全没问题。如果n特别大maxVal可能超出int范围那上面这段就需要改成long版本。4.2 每行开头的空格数倒着算从最后一行反推空格数的核心逻辑是让每一行的内容在水平方向上居中。最笨但最可靠的方法是先算出最后一行的总长度然后每一行开头补上“总长度的一半减去本行长度的一半”的空格。用代码实现可以这样StringBuilder sb new StringBuilder(); // digits 是当前行所有数字空格组成的字符串 int totalWidth (maxWidth 1) * n; // 最终行的近似总宽度 int currentWidth sb.length(); int leadingSpaces (totalWidth - currentWidth) / 2; for (int s 0; s leadingSpaces; s) { System.out.print( ); }这个方法的问题是totalWidth只是估算并非精确的像素级居中但视觉上已经足够。更优雅的做法是先构建最后一行的完整字符串lastLine用它的长度作为基准然后对于第i行先打印(lastLine.length() - currentLine.length()) / 2个空格再打印本行内容。这个方案非常直观而且不依赖任何第三方库。for (int i 0; i n; i) { StringBuilder currentLine new StringBuilder(); for (int j 0; j i; j) { String numStr String.format(%- maxWidth d, triangle[i][j]); currentLine.append(numStr).append( ); } String lastLine buildLastLine(maxWidth, n); int padding Math.max(0, (lastLine.length() - currentLine.length()) / 2); for (int s 0; s padding; s) { System.out.print( ); } System.out.println(currentLine.toString()); }我把buildLastLine单独拎出来做成一个方法因为它要用和当前行完全相同的方式格式化数字否则长度对比就失真了。这个方案的优点是完全可控缺点是每次循环都要重新构建一次最后一行的字符串但这是微秒级的开销完全可以接受。4.3 更“偷懒”但效果不错的制表符方案如果你的目标场景是控制台、而且不追求完美对称直接在每个数字后面跟一个\t制表符也能得到基本可读的输出。制表符的好处是它会自动跳到下一个对齐位置缺点是当数字位数变大时制表符的对齐效果会漂移比如1和300540195的宽度差异很大整个三角形会看起来忽宽忽窄。我的建议是快速验证逻辑时用空格分隔就行要交作业或展示给其他人看时再用maxWidth补位方案。两条路都走一遍你会对“格式化输出”这件事有更深的体感。5. 边界情况与隐蔽陷阱n0、n1、大数值和负数问题写完核心逻辑很多人就直接提交了。但如果测试用例里混入n0、n1这类边界值你的程序很可能当场崩溃。接下来我会逐个列出我实测过的边界场景以及你应该如何修改代码来覆盖它们。5.1 n0应该输出空还是报错如果用户输入0理论上不应该有任何输出。但看看版本一的代码int[][] triangle new int[0][0];这一行没问题可进入打印循环时n是0两个for循环都不会执行程序正常运行输出为空。版本二也一样long[] row new long[0];循环不执行。所以n0时代码“意外地”表现得很安全。但如果你在打印前试图读取triangle[0][0]就会抛出ArrayIndexOutOfBoundsException。因此凡是涉及“读取第0行第0列”来做前置判断的代码都要在读取之前先检查n 0。我还见过有人在输入后直接加了这样一句检查if (n 1) return;。这不算错但会让n0时程序静默退出对用户不太友好。更稳妥的做法是在读取输入后用if (n 0)统一拦截并向用户输出一行提示“行数必须为正整数”然后再返回。5.2 n1只有一行这个看似无聊的用例藏着一个有意思的坑n1时版本一的二维数组是new int[1][1]外层循环i0内层循环j0因为j 0直接赋值1打印输出就是1。版本二更直接row[0] 1L输出1。逻辑上都没有问题。但如果你以前习惯把所有边界判断写在外层循环之前比如提前生成第0行为[1]再从第1行开始循环那你就要非常小心当n1时循环压根不会执行输出也就只有初始化的第0行。这反而没问题。真正容易翻车的写法是把第0行单独初始化然后用for (int i 1; i n; i)从第1行开始这种情况下n1时循环体会执行两次多出一行错误的空数据或越界异常。我的建议是不要在循环外单独初始化第0行把第0行当作第一次外层循环的正常迭代所有行统一处理。这样代码更短也不容易在边界上出问题。5.3 超过int范围后出现的“负数”不是随机故障前文提到过int在n超过34左右就会溢出。我实测了几组数据给一张简单的参考表行数n中间值大约int是否安全10252安全20184756安全30300540195安全342203961430安全但接近上限351166803110安全注意顺序36601080390安全37185248299安全这一行最大值不是中间位置注意n35和n36的中间值反而比n34小这是因为组合数本身随行的变化有起伏吗不是是表格里的“中间值”在不同行对应不同位置而且行与行之间不能简单比较。但总体趋势上第34行的某些值确实接近int上限一旦超过就变成负数。如果你用long替代安全行数能到66左右再往上比如100行、200行就必须引入BigInteger。这里有一个很多人忽视的点即便你用long打印时如果直接调用System.out.print(row[j])Long.toString会自动处理负号所以一旦溢出你会看到负数而不会抛出异常。这导致很多人在测试时根本没发现数据错了直到对答案时才一脸懵。所以如果题目没有明确说明行数上限我强烈建议直接用long并写一个简单的“最大行数检查”超过合理范围就提示用户。6. 从“能打印”到“会演化”把杨辉三角形解成通用工具类题目做着做着你会发现“打印杨辉三角形”这个需求其实可以拆成两个独立的部分计算数据和渲染数据。前者是算法核心后者是UI逻辑。如果能用接口或工具方法把它们分开你的代码不仅更容易测试还能在其他项目里复用。这一节我提供一个稍微进阶一点的写法算是对这个经典题目的一个工程化收尾。6.1 封装一个返回ListList 的生成器最简单的封装方式是写一个方法接收行数n返回一个ListListLong每一行是一个ListLong。这样做的好处是调用方可以自由决定怎么展示数据——打印到控制台、写入文件、渲染成网页表格都行而不需要把算法代码复制三遍。import java.util.ArrayList; import java.util.List; public class YangHuiTriangleGenerator { public static ListListLong generate(int n) { if (n 0) { throw new IllegalArgumentException(行数不能为负数); } ListListLong result new ArrayList(); for (int i 0; i n; i) { ListLong row new ArrayList(); for (int j 0; j i; j) { if (j 0 || j i) { row.add(1L); } else { long left result.get(i - 1).get(j - 1); long right result.get(i - 1).get(j); row.add(left right); } } result.add(row); } return result; } public static void main(String[] args) { ListListLong triangle generate(10); for (ListLong row : triangle) { System.out.println(row); } } }这个版本每次生成新行时直接通过result.get(i - 1)取上一行逻辑非常清晰。代价是ArrayList的装箱和开箱以及引用类型的内存开销。对于n在几十到几百的范围内性能完全不是问题如果你真的需要生成几万行那就该回到一维数组版本。6.2 用Stream流式输出一行顺便聊聊函数式风格如果你喜欢Java 8之后的函数式风格可以尝试用IntStream来生成每一行。下面是一个示例import java.util.stream.IntStream; public static void printRow(ListLong row, int maxWidth) { String line row.stream() .map(num - String.format(%- maxWidth d, num)) .reduce((a, b) - a b) .orElse(); System.out.println(line); }这段代码的可读性比传统for循环差一些但它展示了“数据流”的思路把每个数字格式化成一个定宽字符串再用空格拼接。实际使用时我建议只在格式比较简单的场景用Stream一旦你要同时处理居中对齐、多行缩进传统循环更直观。6.3 通用化之后的另一个妙用把杨辉三角变成“查找单行”的入口生成器一共有整个三角形但如果题目只要求输出第n行你会怎么做最蠢的办法是生成全部再取最后一行稍微聪明一点的办法是用一维数组滚动更新最后只输出row数组的内容。这个函数式一行实现也能做到IntStream.range(0, n).reduce(...)但代码比较绕。我更推荐写一个专门的方法public static ListLong getRow(int rowIndex) { ListLong row new ArrayList(); for (int i 0; i rowIndex; i) { row.add(1L); for (int j i - 1; j 0; j--) { row.set(j, row.get(j - 1) row.get(j)); } } return row; }注意这里的j循环和二维数组版本不同每增加一行就倒序更新row中的已有元素。初始row的add(1L)是在末尾追加一个1正好对应新行的末尾边界内部倒序更新则处理中间的加法。这个方法的时间复杂度是O(n²)空间复杂度是O(n)是“只查一行”场景的最佳方案。7. 时间复杂度、空间复杂度与优化的边界聊完实现最后看一眼复杂度。二维数组版本的时间复杂度是O(n²)因为两层循环各跑了约n次空间复杂度O(n²)因为存了整个三角形。一维数组版本的时间复杂度同样是O(n²)因为循环次数没有减少但空间复杂度降到了O(n)。这里有一个值得思考的问题时间复杂度能不能再优化如果只是打印整个三角形答案是不能低于O(n²)因为光输出就有n行、每行平均n/2个数字输出量本身就是O(n²)。但如果你只需要第n行的某一个数字比如C(n, k)那完全可以用组合数公式直接计算做到O(k)甚至O(1)。具体公式是C(n, k) C(n, k-1) * (n - k 1) / k从C(n, 0)1开始迭代。要注意的是分子分母的计算顺序需要先乘后除否则会丢失精度这是一个常见的细节坑。public static long binomial(int n, int k) { if (k n - k) { k n - k; } long result 1; for (int i 1; i k; i) { result result * (n - k i) / i; } return result; }这段代码里result * (n - k i)可能暂时超过long范围吗在某些边界情况下会所以更稳妥的做法是在循环里用BigInteger或者至少使用long时限制n不超过60左右。这个细节也说明了同一个问题杨辉三角形虽然“简单”但你越往深挖越能碰到数值表示的边界、递推顺序的依赖、格式化输出的一致性问题。这些每一条都是编程基本功的试金石。我实操下来最舒服的学习路径是先用二维数组写一个最朴素的版本跑通然后尝试把它改成不规则数组再改成滚动数组然后再加格式对齐。每改一步都思考一下“这步修改为什么成立”“会不会破坏之前的正确性”。这样走完一遍你对数组、循环、状态依赖的理解会明显上一个台阶以后再碰到“第N行依赖第N-1行”这类题目就不会再觉得难以下手了。