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

文章目录题目链接题目说明解题思路总览解法一二维 DP 表最直观原理流程图Java 代码复杂度分析解法二按行迭代推荐原理时序图Java 代码复杂度分析解法三组合数公式原理Java 代码复杂度分析示例推演numRows 5各解法实现复杂度与性能对比题目链接https://leetcode.cn/problems/pascals-triangle/description/?envTypestudy-plan-v2envIdtop-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解题思路总览杨辉三角核心规律边界恒为1中间左上右上解法一 二维DP表直观便于理解状态转移解法二 按行迭代只依赖上一行代码简洁解法三 组合数公式第i行第j个C(i,j)用递推避免阶乘溢出解法一二维 DP 表最直观原理设dp[i][j]表示第i行第j列0-basedj 0或j i时dp[i][j] 1否则dp[i][j] dp[i-1][j-1] dp[i-1][j]最后把每一行收集到结果列表中。流程图是否否是否是开始创建二维数组 dp 和结果 ansfor i 0..numRows-1for j 0..ij0 或 ji?dp[i][j]1dp[i][j]dp[i-1][j-1]dp[i-1][j]加入当前行本行结束?所有行结束?返回 ansJava 代码importjava.util.*;classSolution{publicListListIntegergenerate(intnumRows){int[][]dpnewint[numRows][numRows];ListListIntegeransnewArrayList();for(inti0;inumRows;i){ListIntegerrownewArrayList();for(intj0;ji;j){if(j0||ji){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中间值来自上一行对应的两个位置相加这是最常见、最清晰的工程写法。时序图ans(结果)cur(当前行)prev(上一行)主循环(i)ans(结果)cur(当前行)prev(上一行)主循环(i)创建长度 i1 的新行填充首尾 1读取 prev[j-1], prev[j]返回两个值计算中间元素并加入cur 入结果prev curJava 代码importjava.util.*;classSolution{publicListListIntegergenerate(intnumRows){ListListIntegeransnewArrayList();ListIntegerprevnewArrayList();for(inti0;inumRows;i){ListIntegercurnewArrayList();for(intj0;ji;j){if(j0||ji){cur.add(1);}else{cur.add(prev.get(j-1)prev.get(j));}}ans.add(cur);prevcur;}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-j1}{j}C(i,j)C(i,j−1)×ji−j1​每一行从1开始递推逐个得到后续元素。Java 代码importjava.util.*;classSolution{publicListListIntegergenerate(intnumRows){ListListIntegeransnewArrayList();for(inti0;inumRows;i){ListIntegerrownewArrayList();longval1;// C(i,0)1for(intj0;ji;j){row.add((int)val);// 计算下一个组合数 C(i, j1)valval*(i-j)/(j1);}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]各解法实现复杂度与性能对比解法核心思想时间复杂度额外空间复杂度不含输出实现复杂度性能表现适用场景二维 DP 表显式保存所有状态O(n²)O(n²)低稳定但内存占用最高教学、初学者理解转移按行迭代只依赖上一行O(n²)O(n)低综合最优代码简洁面试/实战首选组合数公式直接算 C(i,j)O(n²)O(1)中空间最省需注意数值细节追求数学解法、低额外空间结论在这题约束下三种都能轻松通过。推荐优先写“按行迭代”可读性和工程实用性最好。