1. 一题认识杨辉三角：藏在组合数里的规律
1.1 从一道题看数学与编码的交汇
杨辉三角这道题，在LeetCode热题100里属于那种"一看就会，一写就有点东西"的题目。很多人在刷题初期就碰过它，觉得不过是两层循环暴力生成，但真要把它讲清楚，涉及到组合数学、动态规划、边界处理和工程防御，门道其实不少。
这道题的核心诉求很直接：给定一个非负整数numRows，生成杨辉三角的前numRows行。拿最简单的例子说，numRows = 5时输出是这样的：
[1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1]每一行的首尾都是 1，中间每个数是它左上方和右上方两个数的和。这句话听起来就是普通的"下一行由上一行推导"，但它背后其实是高中数学里的二项式系数表。杨辉三角的第 n 行，恰好是二项式展开(a + b)^n的系数序列。比如(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4，系数就是1 4 6 4 1，和上面第四行完全一致。
这也是为什么杨辉三角在LeetCode热题100里占了一个位置：它不只是考察你写循环的能力，更考察你对数学模型的理解程度。如果你能用组合数的视角去看它，很多变种题（比如只求第 k 行、求某个位置的值）都能一击即中。这也是我写这篇文章的初衷：讲透数学本质，再落到 Java 工程实现，让你在面试和实际开发里都能用上。
这篇文章适合三类人：一是刷 LeetCode 的 Java 初学者，想搞懂这类"二维数组递推"题的套路；二是准备面试、想在一道简单题里展现工程素养的求职者；三是在实际项目中需要处理类似"逐层递推、且每层长度递增"这类数据结构的开发者。
1.2 杨辉三角的本质规律拆解
很多人背下了"上方两数相加"的口诀，但没想过它为什么成立。用组合数的话来说，杨辉三角第 n 行第 k 个位置的数值等于组合数 C(n, k)（这里 n 从 0 开始计，k 也从 0 开始计）。核心递推关系是：
C(n, k) = C(n-1, k-1) + C(n-1, k)这个公式在数学上被称为帕斯卡恒等式，它说明的是：从 n 个元素里选 k 个元素，可以拆成"选第 n 个元素，再从剩下的 n-1 个里选 k-1 个"加上"不选第 n 个元素，从剩下的 n-1 个里选 k 个"两种情况。这个组合逻辑非常优雅，也是杨辉三角"每个数等于上方两数之和"的数学证明。
换一个角度看，整个杨辉三角可以看作一个等腰直角三角形网格的左半部分。如果我们把每行左对齐，它其实是一个下三角矩阵。这个矩阵里每个元素的数值只依赖它正上方和左上方两个元素，这种"当前位置只依赖之前已计算好的有限状态"的结构，正是动态规划里的一个基础模型——最简形式的无后效性递推。
在编程实现时，这个递推关系给了我们两套思路：
- 按行递推：用上一行构造当前行，每行长度为行号加 1。时间复杂度 O(n^2)，空间复杂度 O(n^2)（需要保存整个三角）。
- 按组合数公式直接算：第 n 行第 k 列的值为
n! / (k! * (n-k)!)。虽然可以直接计算，但阶乘会很快溢出，而且重复计算量大，工程上不推荐。
两套思路稍后会展开。这里你先记住一个关键点：杨辉三角的第 n 行长度是 n+1，且整张表的数据规模是numRows * (numRows + 1) / 2个元素。这个规模公式在很多优化讨论里都要用到。
2. 题目拆解：LeetCode热题100的考核意图
2.1 题目要求与约束条件分析
LeetCode 官方原题（编号 118）的约束条件很简单：numRows在 1 到 30 之间。输入输出都是二维列表，在 Java 里对应List<List<Integer>>。
这里有一个容易忽略的细节：虽然题面说numRows非负，但官方测试用例通常从 1 开始。不过如果你够严谨，应该自己处理numRows = 0的情况，返回一个空列表。这个边界处理在面试里是加分项。
另一个需要注意的点是返回值类型。List<List<Integer>>意味着每一行是一个独立的List<Integer>，而整个结果又是一个外层List。这个嵌套结构在 Java 里的初始化、遍历、内存占用，都有一些和原地数组不同的讲究。比如你选择用ArrayList还是LinkedList作为每行的容器，虽然这道题都能跑通，但性能特征完全不同。
考核意图可以从三个层面理解：
- 基础层：考察你是否能用循环正确建模递推关系，索引别弄错。
- 进阶层：考察你是否理解时间和空间复杂度的取舍，比如能否写出"只保留上一行"的版本。
- 工程层：考察你在真实代码里的防御能力——输入非法时怎么办？Integer 溢出风险你知道吗？动态扩容的性能开销你考虑过吗？
这三点分别对应普通刷题、面试考察、生产落地三种场景。LeetCode 热题 100 把这道题放进来，因为它很适合作为"从数学模型到工程实现"的教学载体，简单但延展性强。
2.2 边界条件与常见误区
我先说三个最常见的翻车点：
第一，索引偏移。不少人把行号和列号从 1 开始计数，但 Java 数组和链表的下标从 0 开始。第 0 行只有[1]；第 1 行的中间位置要取值时，用的是第 0 行的索引 0。如果你推导递推公式时用的是数学下标，写代码时忘了减 1，很容易数组越界。
第二，行首行尾的 1 被重复计算。很多人会在循环里把上一行的首尾元素也算进加法，结果得到[2, 2, ...]这种错误结果。正确做法是只处理中间索引从 1 到i - 1的元素，首尾手动添加 1。
第三，忘记内层循环从 1 开始。内层循环for (int j = 1; j < i; j++)初值写成了 0，就会尝试访问row.get(-1)，直接抛出IndexOutOfBoundsException。这种错误结构很简单，但一紧张就容易写错，尤其在白板面试时。
针对这些边界问题，我通常建议写代码前先在注释里明确三件事：当前行号i的范围、当前行元素个数i + 1、中间元素索引j的取值范围[1, i - 1]。索引清晰，代码就成功了一半。
3. Java实现方案：从朴素到优雅
3.1 朴素实现：逐行递推的标准写法
先给出最基础的版本。这个版本思路直观，完全按照"每行由上一行生成"的规则来：
public List<List<Integer>> generate(int numRows) { List<List<Integer>> triangle = new ArrayList<>(); if (numRows <= 0) { return triangle; } // 第 0 行：只有一个 1 triangle.add(new ArrayList<>()); triangle.get(0).add(1); for (int i = 1; i < numRows; i++) { List<Integer> row = new ArrayList<>(); List<Integer> prevRow = triangle.get(i - 1); // 行首固定为 1 row.add(1); // 中间元素：上方两个数之和 for (int j = 1; j < i; j++) { row.add(prevRow.get(j - 1) + prevRow.get(j)); } // 行尾固定为 1 row.add(1); triangle.add(row); } return triangle; }这段代码的时间复杂度是 O(numRows^2)，因为第 i 行有 i+1 个元素，所有行加起来是numRows * (numRows + 1) / 2，约等于 O(n^2/2)。空间复杂度同样是 O(numRows^2)，因为整个三角都被保存下来了。
从执行路径来看，每一行的生成只依赖上一行，这意味着这个算法天然支持"流式生成"——如果你只需要某些行，不用把整个三角都留在内存里。但 LeetCode 这题要求返回全部行，所以保存全部是合理的。
3.2 时空复杂度与内存分配的深入分析
很多人做完这道题就过了，没有细想复杂度背后的工程含义。我在这里稍微展开一下。
List<Integer>的实现类选择会直接影响性能：
ArrayList：底层是数组，随机访问快，但尾部扩容有开销。在row.add(prevRow.get(j-1) + prevRow.get(j))这种场景下，每次add都可能触发扩容。LinkedList：插入尾部的时间是 O(1)，但get(j)是 O(j)，也就是说从前往后取中间元素会逐步遍历链表，整体效率远低于ArrayList。
所以这道题应该用ArrayList。但ArrayList也有一个细节：如果不指定初始容量，它默认扩容策略是增长到原容量的 1.5 倍。对于第 30 行这种长度才 31 的列表，扩容不是问题；但如果你的numRows很大（超过了 LeetCode 的约束，比如几万行），每行不断扩容，浪费的时间和内存不可忽视。
顺手算一笔账：numRows = 30时，总共元素个数是 465 个。假设用ArrayList不指定容量，每一行从默认容量 10 开始，中间要经历 10 -> 15 -> 22 -> 33 的扩容，30 行合起来扩容次数虽然不多，但每次都涉及数组复制。如果numRows = 10000，总元素约 5000 万，每一行平均扩容若干次，复制开销就很惊人了。
工程上的优化方法是给每行指定初始容量：
List<Integer> row = new ArrayList<>(i + 1);这样精确预分配，避免扩容。同理，外层triangle也可以指定初始容量new ArrayList<>(numRows)。这是 LeetCode 不考、但实际开发中很有价值的点。
3.3 优化版本：只保留上一行的滚动数组
如果面试官追问："我不需要整个杨辉三角，只需要返回第 k 行，你能把空间复杂度降到 O(k) 吗？"这就引出变种题（LeetCode 119）的核心解法：滚动数组。
思路是只用一个一维数组反复更新。更新时需要从后往前遍历，否则会覆盖掉尚未参与计算的旧值。看代码：
public List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<>(rowIndex + 1); for (int i = 0; i <= rowIndex; i++) { row.add(1); // 从后往前更新 for (int j = i - 1; j >= 1; j--) { row.set(j, row.get(j) + row.get(j - 1)); } } return row; }关键点在于内层循环从i - 1递减到 1。因为新的row[j]需要用到旧row[j]和旧row[j-1]。如果从前往后更新，row[j-1]已经被新值覆盖了，计算就会出错。从后往前更新则能保证用到的两个数都还是上一轮的旧值。
这个技巧在动态规划空间优化里非常常见，比如背包问题的一维数组写法就是同样的思路。理解了这个滚动更新的逻辑，以后再碰到类似的"只依赖前一行"的题目，你都能直接套用。
假设rowIndex = 4，我们手动走一遍：
- 初始
[1] - i=0：
[1] - i=1：
[1, 1] - i=2：先 add(1) 得
[1, 1, 1]，再从 j=1 往前更新：row[1] = row[1] + row[0] = 2，得到[1, 2, 1] - i=3：先 add(1) 得
[1, 2, 1, 1]，j=2 时row[2] = 1 + 2 = 3；j=1 时row[1] = 2 + 1 = 3，得到[1, 3, 3, 1] - i=4：同理得到
[1, 4, 6, 4, 1]
整个流程清晰，空间复杂度 O(k)，时间复杂度仍为 O(k^2)。
4. 工程实践：从LeetCode到生产级代码
4.1 输入验证与防御性编程
LeetCode 的测试用例一般不会给你numRows = -1这种非法输入，但真实世界的接口调用方可不会管这么多。生产代码里，方法入口处加上参数校验是基本素养。
public List<List<Integer>> generate(int numRows) { if (numRows < 0) { throw new IllegalArgumentException("numRows 必须是非负整数，当前值：" + numRows); } List<List<Integer>> triangle = new ArrayList<>(numRows); // ... }这里有多种设计选择：抛出异常、返回空列表、返回Optional等。我的习惯是：如果方法语义上要求必须有返回值，非法参数直接抛IllegalArgumentException，把错误信息写清楚；如果方法允许返回空结果，那么在numRows = 0时返回空列表是合理的。两种做法都行，关键是团队内保持一致。
另一个隐藏问题是Integer溢出。杨辉三角的数值增长非常快，第 30 行的最大数值是 C(30, 15) = 155117520，约 1.5 亿，还在Integer.MAX_VALUE（约 21.47 亿）范围内。但如果numRows超过 34，第 34 行的最大值 C(34, 17) = 2333606220，已经超过Integer.MAX_VALUE，此时 Java 的 int 加法会发生溢出，得到负数。LeetCode 官方约束 1 到 30 避开了这个问题，但你自己扩展功能时一定要注意。
解决方案有两种：一是用long甚至BigInteger替代Integer；二是在循环里增加溢出检测。我的建议是，如果行数控制在 30 以内，Integer完全够用；如果要做通用组件，直接上BigInteger，省得后续排查负数的诡异 bug。
4.2 每行预分配容量与批量填充策略
刚才提到每行用new ArrayList<>(i + 1)来预分配容量。这里再补一个更极致的做法：如果你知道每行的元素值本身都是对称的（杨辉三角左右对称），可以先只计算前半部分，然后镜像复制后半部分，能省一半的加法运算。
public List<Integer> buildRow(int i) { List<Integer> row = new ArrayList<>(i + 1); row.add(1); for (int j = 1; j <= i / 2; j++) { row.add(prevRow.get(j - 1) + prevRow.get(j)); } // 镜像复制 for (int j = i / 2 - 1; j >= 0; j--) { row.add(row.get(j)); } return row; }这个优化对 30 行以内的小数据量提升有限，因为加法本身开销很小，但思路值得借鉴——利用数学对称性减少计算量。在真实项目里，如果你是在循环里做复杂计算，这种优化能带来明显收益。
4.3 扩展到自定义数据结构与序列化输出
在真实项目中，你可能不是直接返回List<List<Integer>>，而是需要写文件、传 JSON、或者进行数据可视化。三个小贴士：
- 如果传输层要求 JSON，直接用 Jackson 或 Gson 序列化
List<List<Integer>>即可，无需额外转换。 - 如果数据量巨大，考虑以流式方式逐行写入，而不是全部堆在内存里。
- 如果后续要对每一行做统计（比如求和、找最大值），可以把方法设计成返回
Stream<List<Integer>>，利用 Java 8 的流式计算。
另外，有些场景需要把杨辉三角用于概率计算（二项分布）。这时候用double存储比例值更合适，比如第 n 行第 k 列对应概率C(n, k) / 2^n。这个用法在随机算法、统计学模拟里很常见。我认为这是杨辉三角最有价值的工程延伸——它不只是刷题玩具，而是一个可以用在真实业务里的数学模型。
5. 常见问题与调试实录
5.1 不同输出形式的性能对比
这里做一个表格，把前面提到的几种实现方式放在一起比较，帮助你面试时快速选择：
| 实现方式 | 时间复杂度 | 空间复杂度 | 适用场景 | 备注 |
|---|---|---|---|---|
| 朴素逐行递推（ArrayList） | O(n^2) | O(n^2) | LeetCode 118 原题 | 最直观，推荐首选 |
| 预分配容量版 | O(n^2) | O(n^2) | 大规模行数 | 减少扩容复制，性能更稳 |
| 滚动数组版 | O(n^2) | O(n) | 只需要第 k 行（LeetCode 119） | 反向遍历是关键 |
| BigInteger 版 | O(n^2) | O(n^2) | 行数超过 34 | 防溢出，但内存占用高 |
这个表格不是让你死记硬背，而是帮你建立"根据需求选方案"的工程思维。面试时说到空间优化，能主动提出"如果只返回第 k 行，可以滚动数组优化到 O(k) 空间"绝对是个加分响应。
5.2 三个实际报错与解决实录
我把实际调试中常见的报错整理成一个速查表：
| 报错信息 | 可能原因 | 解决方案 |
|---|---|---|
IndexOutOfBoundsException | 内层循环j从 0 开始 | 改为从 1 开始，终止条件j < i |
| 输出结果为负数 | Integer溢出，行数超过 34 | 改用long或BigInteger |
| 输出缺少行首或行尾的 1 | 忘记手动添加首尾 | 循环只处理中间元素，首尾单独add(1) |
5.3 一面经验：白板写代码的四个关键步骤
如果你准备用杨辉三角作为面试演示题，我建议按这个流程走：
第一步，先确认输入范围。问面试官：numRows最大多少？是否包含 0？返回值类型有没有要求？这个动作展示了你考虑边界条件的能力。
第二步，画图推导。在白板上写出前四行，理清prevRow.get(j-1) + prevRow.get(j)的索引关系。不要上来就写代码，先建立正确的心智模型。
第三步，先写朴素版本，再提优化。先给出最容易理解的实现，然后主动说："如果只要求返回第 k 行，可以用滚动数组优化空间到 O(k)"。这样既表现出扎实的基础，又表现出优化的意识。
第四步，自查边界。代码写完后，手动代入numRows = 1和numRows = 2跑一遍，确认不会越界。再检查一下numRows = 0的分支。
这套流程我实际试过很多次，它能让你在一道看似简单的题目上体面地展现工程素养，也避免了因为紧张导致低级错误。
6. 踩坑记录：从刷题到项目落地的三个关键心得
6.1 别让"标准答案"限制你的思路
我第一次做这道题时用的是组合数公式直接算，因为当时觉得三行代码很爽：
int value = factorial(n) / (factorial(k) * factorial(n - k));但很快就踩坑了：阶乘计算重复次数太多，numRows = 20时就明显变慢，而且factorial(30)直接溢出。后来改用逐行递推，才真正理解了"动态规划"在其中的意义。这个教训让我明白，LeetCode 的题目不是让你炫技，而是让你在约束条件下选最合适的解法。
6.2 多写一层封装，未来不后悔
在实际项目里，我通常不会把算法逻辑裸写在 Controller 或 Service 里，而是封一层工具类：
public final class PascalTriangle { private PascalTriangle() {} public static List<List<Integer>> generate(int numRows) { // 校验 + 生成 } public static List<Integer> getRow(int rowIndex) { // 滚动数组 } }这样无论是写单测、做性能基准测试，还是将来换用更高效的算法，都可以在不影响调用方的前提下替换实现。LeetCode 上的代码追求"能跑"，生产环境的代码追求"能维护"，这两者的区别值得你体会。
6.3 遇到数值爆炸的场景，主动换数据类型
我曾经把一个内部工具的行数参数调到 40，结果输出里出现了负数。排查后才发现int溢出。后来我直接把整个实现切到long，才算消停。这里我个人的建议是：如果你没法严格限制你的调用方传入的行数，宁愿用BigInteger，也别抱着Integer赌运气。多花的那点内存，远不如排查一个莫名其妙的负数 bug 费的心力多。
