K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
杨辉三角是经典算法入门问题,核心特征为每行首尾元素均为1,第i行的第j个元素等于第i-1行第j-1个元素与第j个元素之和,默认行索引和元素索引均从0开始计数。
生成前n行杨辉三角的时间复杂度为O(n²),空间复杂度最优可优化到O(n)
若要直接获取第n行第k个元素的值(0≤k≤n),可以通过组合数公式C(n,k)计算得到,无需生成前n行数据
使用二维数组存储完整杨辉三角时,对于行数i≥2的行,所有非首尾元素的计算逻辑为arr[i][j] = arr[i-1][j-1] + arr[i-1][j],其中j的取值范围是1<j<i
杨辉三角第n行的所有元素之和等于2的n次方,例如第4行元素之和为16