一、先认识杨辉三角

我们先看看它长什么样：

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

• 每一行的最后一个数都是1

• 中间的数字有什么规律？

例如：

1 3 3 1 ↓ ↓ ↓ 下一行： 1 4 6 4 1

实际上：

4 = 1 + 3 6 = 3 + 3 4 = 3 + 1

也就是说：

杨辉三角中间的每一个数字，都等于它左上方和右上方两个数字之和。

这就是我们今天最重要的递推关系。

二、把杨辉三角看成一个“数字金字塔”

假设我们用二维数组保存：

int a[10][10];

那么：

a[i][j]

表示：

第i行、第j个数字。

为了方便，我们从0开始编号。

例如：

第0行： 1 第1行： 1 1 第2行： 1 2 1 第3行： 1 3 3 1

那么：

a[3][1] = 3

它上面的两个数字是：

a[2][0] = 1 a[2][1] = 2

所以：

a[3][1] = a[2][0] + a[2][1];

再比如：

1 2 1 \ / 3

所以：

a[3][1] = a[2][0] + a[2][1];

这是不是已经很像DP了？

三、杨辉三角其实就是一个最简单的 DP

什么叫 DP？

初学者可以先记住一句非常重要的话：

DP 就是：把大问题拆成小问题，并把小问题的答案保存下来。

杨辉三角特别适合用这个思想。

我们要求：

a[i][j]

只需要知道上一行的：

a[i-1][j-1] a[i-1][j]

于是：

这就是杨辉三角的状态转移方程。

四、第一步：先处理边界

观察：

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

每一行：

第一个 = 1 最后一个 = 1

所以：

a[i][0] = 1; a[i][i] = 1;

中间部分：

a[i][j] = a[i-1][j-1] + a[i-1][j];

于是整个杨辉三角就可以写出来了。

五、C++代码：用 DP 生成杨辉三角

#include <iostream> using namespace std; int main() { int n; cin >> n; int a[100][100] = {}; // 第0行 a[0][0] = 1; // 计算杨辉三角 for (int i = 1; i < n; i++) { // 两边都是1 a[i][0] = 1; a[i][i] = 1; // 计算中间部分 for (int j = 1; j < i; j++) { a[i][j] = a[i - 1][j - 1] + a[i - 1][j]; } } // 输出 for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { cout << a[i][j] << " "; } cout << endl; } return 0; }

输入：

7

输出：

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

六、让小朋友真正看懂“DP在哪里”

我们重点追踪一个数字：

a[4][2]

也就是：

1 4 6 4 1 ↑

它怎么算？

看上一行：

1 3 3 1 \ / 6

所以：

a[4][2] = a[3][1] + a[3][2];

也就是：

a[4][2] = 3 + 3;

得到：

6

再看：

a[5][2]

它又来自：

a[4][1] + a[4][2]

即：

4 + 6 = 10

所以：

a[5][2] = 10

这就是 DP 的核心：

当前答案来自已经计算好的旧答案。

七、其实杨辉三角还有一个非常厉害的身份

我们刚刚一直把它当成一个数字三角形。

但是它还有另外一个身份：

杨辉三角就是“组合数表”。

例如：

第0行： 1 第1行： 1 1 第2行： 1 2 1 第3行： 1 3 3 1 第4行： 1 4 6 4 1 第5行： 1 5 10 10 5 1

实际上：

第 n 行： C(n,0) C(n,1) C(n,2) ... C(n,n)

也就是：

例如：

第5行： 1 5 10 10 5 1

其实就是：

八、为什么会是组合数？

我们先来看：

C(5,2)

是什么意思？

比如有：

A B C D E

从5个人中选择2个人。

有多少种选法？

答案是：

C(5,2) = 10

而杨辉三角第五行中：

1 5 10 10 5 1 ↑

第三个数字恰好就是：

10

所以：

这就是杨辉三角和组合数之间最重要的关系。

九、为什么组合数也满足“左上 + 右上”？

这就更有意思了。

组合数有一个非常重要的公式：

这正好就是杨辉三角的递推公式！

为什么？

假设：

有 n 个人 要选择 k 个人

我们特别关注其中一个人：

小明

那么选择方案可以分成两类：

情况一：选择小明

既然小明已经选了，那么还需要：

从剩下的 n-1 个人中选择 k-1 个人

所以有：

种。

情况二：不选择小明

那么需要：

从剩下的 n-1 个人中选择 k 个人

所以有：

种。

两种情况加起来：

这就是杨辉三角！

所以可以告诉同学们：

杨辉三角之所以能够这样“两个数相加”，背后其实是组合问题的分类计数。

这就把：

DP → 杨辉三角 → 组合数

全部串起来了。

十、杨辉三角与排列有什么关系？

这里要特别区分：

组合

从 n 个东西里面选 k 个

不考虑顺序：

C(n,k)

例如：

A、B

和：

B、A

算同一种。

排列

如果要考虑顺序：

AB BA

这是两种不同的排列。

排列数：

而组合数：

因此：

这个公式非常重要。

十一、举一个小朋友容易理解的例子

假设有：

A B C D E

选择3个人。

先问：

有多少种选择方法？

不考虑顺序：

C(5,3) = 10

也就是杨辉三角中的：

1 5 10 10 5 1 ↑

答案：

10

但是如果问：

从5个人中选3个人，并且排成一个队伍，有多少种方法？

这时候顺序就重要了。

例如：

ABC ACB BAC BCA CAB CBA

同样的三个人，可以排列：

3! = 6

种。

所以：

即：

10×6=60

所以：

十二、杨辉三角与二项式定理

现在进入最精彩的部分。

先看：

等于：

1

对应杨辉三角第0行：

1

再看：

展开：

a+b

系数：

1 1

对应杨辉三角第1行。

再看：

展开：

系数：

1 2 1

对应杨辉三角第2行。

再看：

展开：

系数：

1 3 3 1

对应杨辉三角第3行。

所以我们发现：

杨辉三角的第 n 行，就是展开之后各项的系数。

十三、二项式定理到底是什么？

它告诉我们：

初学者不需要一上来就被这个公式吓到。

可以把它理解成：

展开时，前面的数字系数，就是杨辉三角第 n 行。

例如：

直接查杨辉三角第5行：

1 5 10 10 5 1

所以：

的展开式系数就是：

1 5 10 10 5 1

也就是：

十四、为什么展开式的系数恰好是组合数？

这才是最值得给大家讲清楚的地方。

假设：

其实就是：

(a+b)(a+b)(a+b)

如果我们想得到：

意味着：

三个括号中，有两个选择了a，一个选择了b。

例如：

第1个括号：a 第2个括号：a 第3个括号：b

得到：

aab

也可能：

aba

或者：

baa

一共有：

C(3,1)=3

种。

所以：

前面的系数就是：

3

于是：

这就是二项式定理和组合数之间的关系。

十五、把三个知识点彻底串起来

现在我们可以画出一条非常漂亮的知识链：

杨辉三角 │ ┌─────────┼─────────┐ ↓ ↓ ↓ DP 组合数 二项式定理 │ │ │ │ C(n,k) (a+b)^n │ │ │ └────递推关系───────┘ │ ↓ C(n,k)=C(n-1,k-1)+C(n-1,k)

再进一步：

杨辉三角第 n 行 ↓ C(n,0) C(n,1) ... C(n,n) ↓ (a+b)^n 的系数 ↓ 排列组合计算

这就是为什么一个小小的杨辉三角，能够连接这么多知识。

十六、从 C++ 角度看：这是一个非常好的 DP 入门知识

我特别给初学 C++ 的孩子强调：

杨辉三角不是为了“背公式”，而是为了学习 DP 的思想。

我们可以把它写成：

状态

a[i][j]

表示：

第i行第j个数。

初始状态

a[0][0] = 1;

边界

a[i][0] = 1; a[i][i] = 1;

状态转移

a[i][j] = a[i-1][j-1] + a[i-1][j];

最终结果

整个二维数组

这其实已经是非常标准的 DP 五步思维：

① 定义状态 ↓ ② 找初始值 ↓ ③ 找边界 ↓ ④ 找状态转移 ↓ ⑤ 按顺序计算

以后学：

• 斐波那契数列

• 爬楼梯

• 01背包

• 完全背包

• 路径问题

• 最长公共子序列

都会反复使用这种思想。

十七、再给大家一个非常重要的思维升级

杨辉三角有两种完全不同的“看法”。

第一种：数学家的眼睛

看到：

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

想到：

组合数 二项式定理

第二种：程序员的眼睛

看到：

a[i][j]

想到：

a[i][j] = a[i-1][j-1] + a[i-1][j];

想到：

二维数组 递推 状态 DP

所以我很喜欢用杨辉三角给孩子讲 DP，因为它恰好是：

“数学规律”第一次变成“程序算法”的一个绝佳例子。

十八、最后可以给小朋友留下4道思考题

思考题1：求杨辉三角

输入：

10

输出前10行杨辉三角。

思考题2：求组合数

输入：

5 2

利用杨辉三角求：

C(5,2)

答案：

10

思考题3：求二项式展开式的系数

问：

中间的系数是什么？

只需要找到：

杨辉三角第8行

即可。

思考题4：从组合走向排列

有n个人，选出k个人排成一列。

问有多少种方法？

先利用杨辉三角求：

C(n,k)

然后：

这样，一个知识点就完成了从：

杨辉三角 ↓ 二维数组 ↓ 递推 ↓ DP ↓ 组合数 ↓ 排列数 ↓ 二项式定理

的一次完整串联。