LeetCode Hot100（66/100）——118. 杨辉三角

题目链接

https://leetcode.cn/problems/pascals-triangle/description/?envType=study-plan-v2&envId=top-100-liked

题目说明

给定一个非负整数numRows，生成「杨辉三角」的前numRows行。

杨辉三角规则：

• 每行第一个和最后一个数字都是1
• 中间位置满足：triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]

示例（numRows = 5）：

[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

约束（LeetCode 常见约束）：1 <= numRows <= 30

解题思路总览

解法一：二维 DP 表（最直观）

原理

设dp[i][j]表示第i行第j列（0-based）：

• j == 0或j == i时，dp[i][j] = 1
• 否则：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

最后把每一行收集到结果列表中。

流程图

Java 代码

importjava.util.*;classSolution{publicList<List<Integer>>generate(intnumRows){int[][]dp=newint[numRows][numRows];List<List<Integer>>ans=newArrayList<>();for(inti=0;i<numRows;i++){List<Integer>row=newArrayList<>();for(intj=0;j<=i;j++){if(j==0||j==i){dp[i][j]=1;}else{dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}row.add(dp[i][j]);}ans.add(row);}returnans;}}

复杂度分析

• 时间复杂度：O(numRows^2)
• 空间复杂度：O(numRows^2)（二维表 + 输出）

解法二：按行迭代（推荐）

原理

只保存“上一行”，生成“当前行”：

• 当前行首尾是1
• 中间值来自上一行对应的两个位置相加

这是最常见、最清晰的工程写法。

时序图

Java 代码

importjava.util.*;classSolution{publicList<List<Integer>>generate(intnumRows){List<List<Integer>>ans=newArrayList<>();List<Integer>prev=newArrayList<>();for(inti=0;i<numRows;i++){List<Integer>cur=newArrayList<>();for(intj=0;j<=i;j++){if(j==0||j==i){cur.add(1);}else{cur.add(prev.get(j-1)+prev.get(j));}}ans.add(cur);prev=cur;}returnans;}}

复杂度分析

• 时间复杂度：O(numRows^2)
• 额外空间复杂度：O(numRows)（不算输出，仅上一行临时存储）
• 若计入输出，整体仍为O(numRows^2)

解法三：组合数公式

原理

杨辉三角第i行（0-based）第j个数就是组合数：

C ( i , j ) C(i, j)C(i,j)

使用递推避免直接阶乘：

C ( i , j ) = C ( i , j − 1 ) × i − j + 1 j C(i, j) = C(i, j-1) \times \frac{i-j+1}{j}C(i,j)=C(i,j−1)×ji−j+1​

每一行从1开始递推，逐个得到后续元素。

Java 代码

importjava.util.*;classSolution{publicList<List<Integer>>generate(intnumRows){List<List<Integer>>ans=newArrayList<>();for(inti=0;i<numRows;i++){List<Integer>row=newArrayList<>();longval=1;// C(i,0)=1for(intj=0;j<=i;j++){row.add((int)val);// 计算下一个组合数 C(i, j+1)val=val*(i-j)/(j+1);}ans.add(row);}returnans;}}

复杂度分析

• 时间复杂度：O(numRows^2)
• 额外空间复杂度：O(1)（不计输出）
• 需注意中间计算建议用long

示例推演（numRows = 5）

第0行: [1] 第1行: [1, 1] 第2行: [1, 2, 1] 第3行: [1, 3, 3, 1] 第4行: [1, 4, 6, 4, 1]

各解法实现复杂度与性能对比

结论：
在这题约束下，三种都能轻松通过。推荐优先写“按行迭代”：可读性和工程实用性最好。