1. 杨辉三角到底考的是什么：从数学本质到题目定位
我在刷LeetCode热题100的时候，对杨辉三角这题印象特别深。因为它看起来就是一个二维数组的填充题，好像几行代码就能写完，但仔细琢磨之后发现，这道题的考察点远不止“会不会写循环”这么简单。
杨辉三角在LeetCode上其实有两道题，一道是给行数生成完整三角形，另一道是只输出某一行的结果。热题100里收录的是前一道，也就是用Java实现完整的杨辉三角生成。题目描述非常直白：输入一个非负整数numRows，生成杨辉三角的前numRows行。比如输入5，输出就是：
[1] [1,1] [1,2,1] [1,3,3,1] [1,4,6,4,1]很多人第一反应是：这不就是二维数组的双层循环吗？确实，最朴素的解法就是双层循环，外层控制行数，内层控制列数，每一行的首尾都填1，中间位置填上一行相邻两个数的和。但我建议你不要急着写代码，先搞清楚这道题背后的三个关键词：递推关系、边界处理、集合操作的熟练度。
先说递推关系。杨辉三角最核心的数学本质是组合数学中的二项式系数表，第n行第k个位置的值等于组合数C(n, k)，也就是从n个不同元素中取k个元素的组合数。这个值满足一个关键递推公式：C(n, k) = C(n-1, k-1) + C(n-1, k)。注意，这个公式到代码里就变成了triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]，这就是杨辉三角每一行中间元素怎么来的。当年帕斯卡研究这个三角形的时候，就是用这个递推关系手算组合数，避免了阶乘的庞大计算量。理解了这一点，你就明白为什么杨辉三角在算法题里常被当作“动态规划入门题”来用——它本质上就是一个线性递推问题。
再说边界处理。每行首尾都是1，这是数学定义决定的，因为C(n, 0) = 1且C(n, n) = 1。这个边界条件看似简单，但很多人在写循环条件时容易搞混——到底是j <= i还是j < i？到底是先填充再判断首尾，还是先判断首尾再填充？这些细节我在下文会详细展开。
最后说集合操作。如果你用Java解这道题，最自然的做法是用List<List<Integer>>来存储结果，而不是传统的二维数组。为什么？因为杨辉三角的行长度是动态变化的，每行比上一行多一个元素，这种“不规则二维结构”用集合来建模比用数组方便得多。但这也引出一个新手很容易踩的坑：List里存的都是对象的引用，你如果反复操作同一个ArrayList对象，会把之前添加的行全部改掉。这就是为什么比较靠谱的写法是每行都new ArrayList<>()，而不是复用一个list再clear()。
这道题适合谁去认真研究？我建议三类人重点看：一是正在准备笔试面试的应届生，因为杨辉三角经常被作为“考察递推和边界条件的引入题”，而且很多大厂会在此基础上问扩展问题，比如只输出某一行怎么优化空间；二是刚学Java集合框架不久的人，这道题能帮你理清List、ArrayList、get、set、add这些常用操作在实际场景下的配合；三是想搞懂“数学公式怎么落地成代码”的人，因为杨辉三角是少有的、不需要任何数据结构基础、纯靠递推就能解出来的好题目。
我在实际刷题过程中发现，如果能把这题的多种解法都写一遍——朴素二维数组、滚动数组、直接用组合数公式、单行递推——你对Java的数组和集合操作会有一次质的提升。而且它的应用还延伸到概率论里的二项分布、多项式展开系数、甚至某些图像处理里的网格路径计数问题。所以别小看这题，它值得你花半小时好好拆解。
2. Java实现的核心细节：从List到二维数组的完整拆解
2.1 最朴素的双层循环写法与边界条件分析
我们先从最经典的写法开始。用List<List<Integer>>存结果，外层循环控制行数，内层循环控制当前行的每一列，完整代码如下：
public List<List<Integer>> generate(int numRows) { List<List<Integer>> triangle = new ArrayList<>(); if (numRows == 0) { return triangle; } triangle.add(new ArrayList<>()); triangle.get(0).add(1); // 第一行固定是[1] for (int i = 1; i < numRows; i++) { List<Integer> row = new ArrayList<>(); List<Integer> prevRow = triangle.get(i - 1); row.add(1); // 当前行第一个元素永远是1 for (int j = 1; j < i; j++) { row.add(prevRow.get(j - 1) + prevRow.get(j)); } row.add(1); // 当前行最后一个元素永远是1 triangle.add(row); } return triangle; }这里有个关键细节：为什么内层循环是j < i而不是j <= i？因为当前行有i + 1个元素，下标从0到i。我们已经手动添加了第0个元素（开头的1），所以循环从1开始；又因为最后一个元素（下标i）也是手动添加的1，所以内层循环只需要算中间部分，也就是下标1到i - 1。这段区间的长度恰好是i - 1，循环条件写成j < i刚好覆盖1到i-1。如果你写成j <= i，就会在最后一次循环时尝试访问prevRow.get(i)，而上一行只有i个元素，下标最大是i - 1，直接越界。
我个人在帮别人review代码时，见过最多的错误就是这里。很多人知道首尾要填1，但内层循环的范围没想清楚，要么少了最后一个中间元素，要么数组越界。建议你在脑子里过一遍具体例子：i = 2时（第三行），当前行应该有3个元素，前两个分别是[1, 2]，最后一个补1变成[1, 2, 1]。内层循环j = 1，只执行一次，prevRow.get(0) + prevRow.get(1)，即1 + 1 = 2，完全正确。
2.2 参数选择：为什么用List<List<Integer>>而不是int[][]
有人会问，二维数组不也能存杨辉三角吗？确实能，但有一个很麻烦的问题：你必须在创建数组时就确定每一行的长度。Java的二维数组本质上是“数组的数组”，每一行可以有不同的长度，也就是所谓的“不规则数组”。所以你可以这样写：
int[][] triangle = new int[numRows][]; for (int i = 0; i < numRows; i++) { triangle[i] = new int[i + 1]; triangle[i][0] = 1; triangle[i][i] = 1; for (int j = 1; j < i; j++) { triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]; } }这段代码本身是没问题的，LeetCode上也能通过，而且运行速度比List版本更快——因为int[]是连续内存，访问效率远高于对象类型。但LeetCode的返回值类型是List<List<Integer>>，你要么直接在函数里用List，要么最后把二维数组手动转成嵌套List。很多追求极致性能的人会选择后者，毕竟转换成List的开销并不大。
那为什么标准答案基本都用List？原因有三点。其一，LeetCode题目的类型签名就是List<List<Integer>>，直接用List避免多余的转换代码，让解题逻辑更清晰；其二，List的add操作会自动扩容，动态生成每一行时不需要你提前知道行的具体长度，代码更简洁；其三，在面试场景中，用List体现的是对集合框架的熟悉程度，而集合框架恰恰是Java面试的重点考察方向。我给一个折中建议：如果你是初学者，就用List版本先跑通逻辑；等你想优化性能了，再去尝试二维数组版本，感受一下两种写法在内存和时间上的差异。
不过有一个地方要特别提醒：如果你选择了List<List<Integer>>，千万不要试图复用同一个ArrayList对象来添加每一行数据。比如你写成：
List<Integer> row = new ArrayList<>(); for (int i = 0; i < numRows; i++) { row.clear(); // 填充row... triangle.add(row); }这种写法是典型的“引用陷阱”。你往triangle里添加的是row对象的引用，而非值拷贝。clear()清空的是同一个对象里的数据，之前已经加入triangle的那些行也会跟着变成空列表。最终打印出来的triangle会是一堆空集合。这也是Java新手在用List存列表时最容易踩的坑。正确的做法就是每行都新建一个ArrayList，所谓“行行都是新生”，绝不复用。
2.3 转置思维：反向填充时的边界改法
有些扩展题目会把杨辉三角变形成“从底部向上输出”或“输出第k行”，这时候很多人的习惯是先把整个三角形算出来再取行。这个思路没错，但不够优雅。比如LeetCode第119题“杨辉三角II”，要求只返回第rowIndex行，且要求空间复杂度优化到O(rowIndex)。一种很聪明的做法是从最后一行往前面算，利用一个长度为rowIndex + 1的数组反复覆盖。
这里我分享一个反直觉的写法——从右往左更新。假设我们已经有了上一行的结果存在长度为n的列表里，要算当前行的前n个元素，只需要在当前列表上原地更新：
public List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<>(); for (int i = 0; i <= rowIndex; i++) { row.add(0, 1); // 在头部插入1，所有元素右移 for (int j = 1; j < i; j++) { row.set(j, row.get(j) + row.get(j + 1)); } } return row; }等等，这段代码用add(0, 1)确实能在头部插入1，但后续的更新逻辑就要调整，因为所有元素的下标都右移了一位。我不建议用这个版本，太绕了。更稳妥的思路是正向计算，每次在末尾追加1，然后从右往左更新不覆盖前面的值。你可以在纸上模拟一下：当前行是[1, 3, 3, 1]，要生成下一行，先在末尾追加1得到[1, 3, 3, 1, 1]，然后从倒数第二个位置开始往前更新，j=3时把原第3位变成原第2位+原第3位，即3 + 1 = 4，得到[1, 3, 3, 4, 1]；j=2时把原第2位变成3 + 3 = 6，得到[1, 3, 6, 4, 1]；j=1时把原第1位变成1 + 3 = 4，最终得到[1, 4, 6, 4, 1]。这就是“滚动数组原地覆盖”的经典思路，从右往左更新确保每个位置的旧值在被覆盖之前已经参与过计算。
这个思路和二维数组转置问题的核心理念是一致的——当你需要在原地操作时，一定要搞清楚数据依赖的方向。杨辉三角的依赖方向是从上一行到下一行、从左到右，如果你原地覆盖时也按照从左到右更新，就会把还没用到的旧值提前覆盖掉，得到全错的结果。这个教训在动态规划题目里尤其常见，比如背包问题的一维优化，也是同样的逻辑。
3. 空间复杂度的进阶：从O(n²)到O(n)的两种套路
3.1 滚动数组：只保留前一行
如果你只需要输出杨辉三角的最后一行，或者只需要在工程代码中计算某一行用于组合数运算，就不必把整个三角形都存下来。滚动数组就是只保留“上一行”的数据，每次计算完当前行就将容器引用替换一下。
public List<Integer> getRow(int rowIndex) { List<Integer> prev = new ArrayList<>(); for (int i = 0; i <= rowIndex; i++) { List<Integer> curr = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { curr.add(1); } else { curr.add(prev.get(j - 1) + prev.get(j)); } } prev = curr; } return prev; }这段代码的时间复杂度仍然是O(rowIndex²)，但空间复杂度降到了O(rowIndex)——因为任意时刻内存里只有两行数据。看到这里你可能会想：能不能再极限一点，只用一个列表就搞定？完全可以，这就是右文提到的“原地覆盖”版本，空间复杂度同样是O(n)，但连prev和curr两个引用的切换都省了，代码也更短。唯一要注意的就是更新方向必须从右往左，否则会覆盖旧值。我建议两种写法都练习一遍，面试时如果被问到“如何优化空间”，你就直接说两个版本，还能顺势展开讲一讲动态规划空间压缩的通用套路，这是一个很好的加分点。
3.2 直接用组合数公式：C(n, k)的递推计算
杨辉三角第n行第k列的值是C(n, k)，而组合数本身还有一个递推公式：C(n, k) = C(n, k-1) * (n - k + 1) / k。利用这个公式，可以在O(n)时间内算出某一行所有元素，而且只需要O(1)额外空间（不算存结果的空间）。
public List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<>(); long val = 1; for (int k = 0; k <= rowIndex; k++) { row.add((int) val); val = val * (rowIndex - k) / (k + 1); } return row; }注意我用了long来存中间结果。为什么要用long？因为val * (rowIndex - k)这个乘法可能临时超过int的最大值。比如rowIndex = 30，第15个组合数大约是1.55亿，乘以(30-14)=16得到24.8亿，已经超过21亿的int上限了。虽然最终除以(k+1)之后会缩小，但中间乘法溢出是真实存在的坑。我在用这个公式刷第119题时，第一次就用int存，结果在高行数时出现了负数，排查了半天才发现是溢出。后来统一用long，再在add时强转回int，问题迎刃而解。
这个公式还有一个工程应用场景：在实现二项分布概率计算时，比如P(X=k) = C(n,k) * p^k * (1-p)^(n-k)，中间需要计算组合数，用这个递推公式比硬算阶乘高效得多，也避免了阶乘溢出问题。如果你在某个数据分析项目里需要计算伯努利试验的概率分布，这个写法可以直接抄。
3.3 性能和精度的取舍：什么时候选暴力阶乘
有人会用阶乘公式直接计算：C(n, k) = n! / (k! * (n-k)!)。这种方法在理论上很简单，但在计算机上非常容易溢出。Java的long最大约9.2×10^18，20!就已经超过这个范围了。所以如果n > 20，直接用阶乘公式几乎必然溢出。这时有两个选择：一是用BigInteger，但性能差很多，而且代码冗长；二是用递推式，避免大阶乘的中间膨胀。
我在实际工程里处理组合数时，基本只用两种方式：n较小（小于30）时用上面提到的O(n)递推；n较大但只需要一个值或很少的几个值的时候，用对数近似或者直接上BigInteger，但会限制调用频率。因为BigInteger的加减乘除开销比原始类型高一个数量级，频繁调用会严重影响性能。这里没有绝对的最优解，关键是清楚你的数据规模和应用场景。
4. 题目变形与工程实践：从LeetCode到真实项目的延展
4.1 LeetCode第119题的“只输出第k行”变体
热题100里没收录第119题，但这道变形题出现频率相当高。它要求给定非负索引rowIndex，返回杨辉三角第rowIndex行。最容易想到的做法是直接复用原题代码，生成完整三角形再取行。这样代码简单，但空间复杂度是O(k²)，冗余明显。
更好的做法是用上一节说的滚动数组或组合数递推公式。我自己在面试现场写这题时，习惯先写出滚动数组版本，因为思路和原题一脉相承，面试官容易跟上。写完之后，我会补充一句：“如果追求极致，还可以用组合数递推，空间O(k)，时间O(k)，代码更短。”然后等面试官追问再展开。这样既展示了基础能力，又暴露了深入思考。但要注意，第119题的rowIndex是从0开始的，也就是说第0行是[1]，这一细节和原题的numRows（从1开始计数）不同，写代码前先确认清楚，省得循环次数少算一行。
4.2 工程场景：杨辉三角式网格路径计数
杨辉三角的应用远不止刷题。我举一个实际场景：假设你在开发一个棋盘类游戏，需要计算从棋盘左上角走到右下角有多少种走法，每一步只能向右或向下移动一格。这个问题的答案就是组合数C((m-1)+(n-1), m-1)，因为一共要走m-1步向下和n-1步向右，只需要决定哪几步是向下的。它的数值表恰好就是杨辉三角的形状——把棋盘旋转45度看，每个格子的路径数就是杨辉三角的某个值。
我在某个路径规划的模拟项目里就用到了这个性质。当时的需求是计算不同尺寸网格下的路径数量，用来评估搜索算法的复杂度。最初打算用动态规划逐一计算，后来发现直接查杨辉三角表更快——生成到第50行的表，任何规模不超过50×50的网格路径数都能在O(1)时间查到。这个思路在很多“计数组合”类问题里都能复用。杨辉三角和动态规划的关系非常紧密，甚至可以说它就是最原始的动态规划模型：每一行的值依赖于上一行，状态转移方程清晰可见。如果你正在学习动态规划，把这题吃透，再看背包问题、硬币找零问题，会明显轻松一些。
4.3 慎用嵌套数据结构：冗余包装与内存开销提醒
Java的List<List<Integer>>虽然在刷题时方便，但在工程中要慎用。每个ArrayList对象都有自己的对象头、元素数组、modCount等字段，嵌套几层之后，内存开销远比同规模的int[][]大。如果某个服务需要频繁生成和遍历杨辉三角结构，比如某一行的行数很大，再用List版本可能影响GC性能。此时更合理的设计是：内部使用int[][]高效计算，对外只暴露必要的只读视图，或者将结果序列化传输。
我在一个内部数据展示模块中遇到过这种情况：接口每次要返回一个三角形结构，最初用List<List<Integer>>直接返回给前端，压测时发现大流量下GC频率明显偏高。后来改成后端用int[][]计算，再在返回前一次性转换成前端需要的JSON结构，内存申请次数大幅下降。这个案例说明，刷题时求简洁，工程中求可控，两种取舍完全不同。你准备面试时讲项目，如果能主动提到这个优化点，面试官会觉得你不但会写算法，还懂工程折中。
4.4 杨辉三角与二项展开、概率分布的联动
再拓展一下视野。杨辉三角第n行的数值，恰好是(a + b)^n二项展开式的各项系数。比如(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3，系数1, 3, 3, 1就是第3行。这个联系在数学上非常优美，也是杨辉三角被称为“帕斯卡三角形”的原因。在工程中，如果你需要快速展开某个多项式的幂，可以预先算好系数表，避免重复计算组合数。
同理，二项分布的概率质量函数P(X=k) = C(n,k) * p^k * (1-p)^(n-k)也和杨辉三角直接相关。比如做一个A/B测试，实验组人数为100，预期转化率为0.2，要估算转化人数落在某个区间的概率，就需要批量计算组合数。用滚动数组按行生成，比逐个调用阶乘函数快得多，还天然规避了溢出问题。我建议每个做数据分析和后端开发的工程师，都把这段知识串起来，未来大概率用得上。
5. 常见问题排查与实战心得
5.1 高频错误速查表
我整理了这份题目最常见的错误，以及对应的原因和解决方案，直接对照检查就行。
| 错误现象 | 根本原因 | 解决方式 |
|---|---|---|
| 输出多了最后一行、少了第一行 | 循环范围没对齐：numRows是按行数计数，rowIndex是按从0开始的索引计数 | 用numRows时循环i < numRows；用rowIndex时循环i <= rowIndex |
| 数组越界异常 | 内层循环访问了上一行不存在的下标 | 内层循环范围控制在j < i；访问prevRow.get(j - 1)和prevRow.get(j)前确保j - 1 >= 0且j < prevRow.size() |
| 结果全是空列表 | 复用了同一个ArrayList对象，加入triangle的是引用而非拷贝 | 每行new ArrayList<>()；如果用clear()，先意识到它把旧数据也清掉了 |
| 中间结果出现负数 | 使用组合数递推公式时，乘法溢出 | 中间变量用long，在add时再转回int |
| 只输出某一行时结果错乱 | 原地覆盖时从左往右更新，覆盖了尚未参与计算的旧值 | 原地更新一定要从右往左；或使用滚动数组双列表方案 |
| 输出格式多了逗号或分号 | 打印时误用了println(row)的默认格式 | toString()展示即可；如果有特殊格式需求，手动拼接StringBuilder |
5.2 调式技巧：用可视化输出验证小规模数据
调试杨辉三角非常简单，关键是构造小规模用例并手动验证。比如输入numRows = 6，提前在纸上写出正确结果：
[1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1]然后写一个打印函数：
for (List<Integer> row : triangle) { System.out.println(row); }逐行对比。如果第二行就出错，说明递推公式写错了；如果最后一行的中间几个值不对，大概率是内层循环边界或者更新顺序问题。我调试时还有一个习惯：在每个关键步骤临时打印中间状态，比如在row.add(prevRow.get(j - 1) + prevRow.get(j))这一行后面加一行注释掉的打印，确认进入循环时prevRow的内容是否符合预期。对于新手来说，调试不是丢人的事，反而是快速理解代码逻辑的最高效方式。
5.3 实战心得：这道题对动态规划学习的隐喻价值
最后分享一点我对这道题的个人感受。很多人一开始觉得杨辉三角太简单，连动态规划的门槛都够不着，但我恰恰认为它是一个极好的动态规划启蒙题。原因在于它包含了动态规划的全部核心要素：明确的状态定义（第i行第j列的值）、清晰的状态转移方程（上一行两个值相加）、严格的边界条件（首尾为1）和自然的计算方向（从小到大逐行推进）。
等你学完背包问题再回来看杨辉三角，会发现背包问题本质上也是“依赖上一阶段的某个状态组合”，区别只是状态转移方程和维度不同。我还观察到，公司面试题中出现杨辉三角的变体时，面试官往往并不指望你背出答案，而是希望看到你在不熟悉场景下的分析过程。这时候，如果你能把“递推关系、边界条件、空间优化”这三点讲清楚，即便代码有小瑕疵，整体印象也会很好。
我在实际刷题过程中踩过一次比较典型的坑，就是在做第119题时横向复用了一个列表，从左往右原地更新，结果整行的数据全部被污染。当时排查了很久才发现是更新方向的问题。从那以后，凡是遇到原地覆盖的题目，我都会先画一张依赖图，确定哪些旧值在被覆盖前还需要被使用，然后再决定遍历方向。这个习惯后来在我做很多动态规划优化题目时帮了大忙，希望对你也有参考价值。
提示：如果你自己动手把这道题的四种解法都写一遍——朴素二维数组、嵌套List版本、滚动数组、组合数递推——再对比它们的时间和空间消耗，你对Java数据结构的理解一定会上升一个台阶。强烈建议别只抄答案，亲手每种都跑一遍。
