“杨辉三角不是一张神奇的数字表而是一台会不断产生下一行数字的机器。”一、先认识杨辉三角我们先看看它长什么样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]于是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八、为什么会是组合数我们先来看C(5,2)是什么意思比如有A B C D E从5个人中选择2个人。有多少种选法答案是C(5,2)10而杨辉三角第五行中1 5 10 10 5 1 ↑第三个数字恰好就是10所以a[n][k] C(n,k)这就是杨辉三角和组合数之间最重要的关系。九、为什么组合数也满足“左上 右上”这就更有意思了。组合数有一个非常重要的公式C(n,k) C(n-1,k-1) C(n-1,k)这正好就是杨辉三角的递推公式为什么假设有 n 个人 要选择 k 个人我们特别关注其中一个人小明那么选择方案可以分成两类情况一选择小明既然小明已经选了那么还需要从剩下的 n-1 个人中选择 k-1 个人所以有C(n-1,k-1)种。情况二不选择小明那么需要从剩下的 n-1 个人中选择 k 个人所以有C(n-1,k)种。两种情况加起来C(n,k) C(n-1,k-1) C(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种。所以P(5,3) C(5,3) * 3!即10 * 660所以P(5,3) 60十二、杨辉三角与二项式定理现在进入最精彩的部分。先看(ab)^0等于1对应杨辉三角第0行1再看(ab)^1展开ab系数1 1对应杨辉三角第1行。再看(ab)^2展开a^22abb^2系数1 2 1对应杨辉三角第2行。再看(ab)^3展开a^3 3a^2b 3ab^2 b^3系数1 3 3 1对应杨辉三角第3行。所以我们发现杨辉三角的第 n 行就是 ((ab)^n) 展开之后各项的系数。十三、二项式定理到底是什么初学者不需要一上来就被这个公式吓到。可以把它理解成展开 ((ab)^n) 时前面的数字系数就是杨辉三角第 n 行。例如(ab)^5直接查杨辉三角第5行1 5 10 10 5 1所以(ab)^5的展开式系数就是1 5 10 10 5 1也就是a^55a^4b10a^3b^210a^2b^35ab^4b^5十四、为什么展开式的系数恰好是组合数这才是最值得给孩子讲清楚的地方。假设(ab)^3其实就是(ab)(ab)(ab)如果我们想得到a^2b意味着三个括号中有两个选择了a一个选择了b。例如第1个括号a 第2个括号a 第3个括号b得到aab也可能aba或者baa一共有C(3,1)3种。所以a^2b前面的系数就是3于是(ab)^3 a^3 3a^2b 3ab^2 b^3这就是二项式定理和组合数之间的关系。十五、把三个知识点彻底串起来现在我们可以画出一条非常漂亮的知识链杨辉三角 │ ┌─────────┼─────────┐ ↓ ↓ ↓ DP 组合数 二项式定理 │ │ │ │ C(n,k) (ab)^n │ │ │ └────递推关系───────┘ │ ↓ C(n,k)C(n-1,k-1)C(n-1,k)再进一步杨辉三角第 n 行 ↓ C(n,0) C(n,1) ... C(n,n) ↓ (ab)^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背包完全背包路径问题最长公共子序列都反复使用dp思想。十七、再给同学们一个非常重要的思维升级杨辉三角有两种完全不同的“看法”。第一种数学家的眼睛看到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求二项式展开式的系数问(ab)^8中间的系数是什么只需要找到杨辉三角第8行即可。思考题4从组合走向排列有n个人选出k个人排成一列。问有多少种方法先利用杨辉三角求C(n,k)然后P(n,k) C(n,k) * k!这样这个知识点就完成了从杨辉三角 ↓ 二维数组 ↓ 递推 ↓ DP ↓ 组合数 ↓ 排列数 ↓ 二项式定理的一次完整串联。