杨辉三角：从数学原理到编程实现

1. 杨辉三角的前世今生

第一次接触杨辉三角是在大学离散数学课上，当时只觉得这个数字三角形排列得很漂亮，直到后来学习动态规划才真正理解它的精妙之处。杨辉三角在中国南宋时期由数学家杨辉在《详解九章算法》中记载，比欧洲帕斯卡(Pascal)的发现早了近400年。这个看似简单的数字三角形，实际上蕴含着组合数学的核心奥秘。

杨辉三角的构造规则极其简单：每一行的首尾都是1，中间每个数等于它上方两个数之和。用数学表达式表示就是：

cpp复制C(n, k) = C(n-1, k-1) + C(n-1, k)

这正是组合数的递推公式。举个例子，要计算从5个人中选2个人的组合数C(5,2)，通过杨辉三角可以轻松找到第6行第3个数（注意行列通常从0开始计数），结果是10。

提示：在编程实现时，建议行列索引都从0开始，这样更符合C++数组的索引习惯，也便于与组合数公式对应。

2. 杨辉三角的数学本质

2.1 与组合数的关系证明

杨辉三角的第n行第k个数（从0开始计数）正好等于组合数C(n,k)。这个性质可以通过数学归纳法证明：

1. 基础情况：第0行只有数字1，对应C(0,0)=1
2. 归纳假设：假设第n-1行的数都满足组合数性质
3. 归纳步骤：根据递推关系C(n,k)=C(n-1,k-1)+C(n-1,k)，正好对应杨辉三角的生成规则

这个证明过程也解释了为什么杨辉三角在动态规划中如此重要——它本质上就是一个自底向上计算的递推过程。

2.2 二项式定理的直观展示

杨辉三角的每一行实际上就是二项式(a+b)^n展开式的系数。例如：

code复制(a+b)^3 = 1a³ + 3a²b + 3ab² + 1b³

对应的系数1,3,3,1正好是杨辉三角第3行。这个性质在概率论和代数运算中非常有用。

3. 杨辉三角的编程实现

3.1 基础实现方法

最直观的实现方式是使用二维数组。以下是一个完整的C++实现示例：

cpp复制#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> generatePascalTriangle(int numRows) {
    vector<vector<int>