LeetCode 算法：杨辉三角 c++
- 原题链接🔗：杨辉三角
- 难度：简单⭐️
题目
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
1 <= numRows <= 30
杨辉三角
杨辉三角，又称帕斯卡三角形，是一种将二项式系数以三角形形式排列的数学图形。它在中国最早由北宋数学家贾宪在《释锁算术》中提出，后来南宋数学家杨辉在1261年所著的《详解九章算法》中进行了详细说明，并称之为“开方作法本源”图。杨辉三角不仅揭示了二项展开式的二项式系数的构成规律，还具有许多奇妙的性质，例如每行数字的对称性、中间数字最大等。
杨辉三角的递推公式是每个数等于它上方两个数之和，这一规律被称为杨辉三角的核心。在杨辉三角中，每行的数字之和为 2n - 1，其中 n
是行数，且第 n 行的第 m 个数可以表示为组合数 C(n-1, m-1)。在欧洲，杨辉三角被称为帕斯卡三角形，因为法国数学家帕斯卡在1654年发现了这一规律，这比杨辉晚了393年，比贾宪晚了约600年。杨辉三角在数学、组合数学、概率论等领域都有广泛的应用，并且随着计算机技术的发展，其计算和应用变得更加便捷和高效。
另外，杨辉三角与文学中的宝塔诗和连环章等有着相似之处，展现了数学与文学的交融之美。在编程实现中，杨辉三角也较为容易构造，可以通过简单的递推算法来生成。
题解
- 解题思路：
杨辉三角，又称帕斯卡三角，是一个在数学中非常著名的几何图形，它由数字组成，每行的数字是上一行相邻数字的和。具体来说，杨辉三角的第0行是1，从第1行开始，每个数字是它正上方和左上方的数字之和。例如：
11 11 2 1 1 3 3 1 1 4 6 4 1 ...LeetCode上的杨辉三角问题通常要求你实现一个函数，根据输入的行数返回对应的杨辉三角行。以下是解决这个问题的一种思路：
初始化：首先，你需要一个二维数组来存储杨辉三角的每一行。数组的行数等于输入的行数
rowIndex。填充第一行：杨辉三角的第一行总是
[1]，所以你可以初始化数组的第一行。填充后续行：对于每一行，除了第一个和最后一个元素（它们都是1），其他元素都是其正上方和左上方元素的和。
边界条件：注意，每一行的第一个和最后一个元素都是1，这是杨辉三角的一个特性。
返回结果：最后，返回填充好的二维数组。
- c++ demo：
#include <iostream>
#include <vector>// 函数用于生成杨辉三角的前n行
void generatePascalTriangle(int n) {std::vector<std::vector<int>> triangle;for (int i = 0; i < n; ++i) {std::vector<int> row(i + 1, 1); // 每行开始和结束都是1triangle.push_back(row);// 计算中间的值for (int j = 1; j < i; ++j) {triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];}}// 打印杨辉三角for (const auto& row : triangle) {for (int num : row) {std::cout << num << " ";}std::cout << std::endl;}
}int main() {int numRows;std::cout << "Enter the number of rows for Pascal's Triangle: ";std::cin >> numRows;generatePascalTriangle(numRows);return 0;
}
- 输出结果：
Enter the number of rows for Pascal’s Triangle: 9
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
- 代码仓库地址：generatePascalTriangle