第4章杨辉三角

🎯 本章学习目标

通过本章的学习，你将能够：

理解杨辉三角定义：掌握杨辉三角的结构和递推关系
掌握二维数组实现：能用二维数组递推生成杨辉三角
掌握一维滚动数组：能用一维数组优化空间复杂度
理解组合数对应：知道杨辉三角第n行第m列 = C(n,m)
掌握二项式定理：理解杨辉三角与二项式系数的关系
解决路径计数问题：能用组合数/杨辉三角求解网格路径问题
掌握求和性质：知道第n行数字和为2ⁿ
理解对称性：知道杨辉三角左右对称
边界处理：注意行列从0开始，边界都是1
应对真题题型：能解决选择、判断、编程等各类杨辉三角题目

🗺️ 本章知识图谱

杨辉三角
├── 定义与结构
│   ├── 三角形数阵
│   ├── 第i行有i+1个数
│   ├── 左右对称
│   └── 每行两端都是1
├── 递推关系
│   ├── C(i,j) = C(i-1,j-1) + C(i-1,j)
│   ├── 每个数 = 左上 + 正上
│   └── 边界：C(i,0)=C(i,i)=1
├── 实现方法
│   ├── 二维数组
│   │   ├── dp[i][j] 存储
│   │   ├── 空间 O(n²)
│   │   └── 直观易懂
│   └── 一维滚动数组
│       ├── 从后往前更新
│       ├── 空间 O(n)
│       └── 注意遍历顺序
├── 组合数意义
│   ├── 第n行第m列 = C(n,m)
│   ├── C(n,m) = C(n,n-m)（对称性）
│   └── 第n行和 = 2ⁿ
├── 二项式定理
│   ├── (a+b)ⁿ 展开系数
│   ├── 第k项系数 = C(n,k)
│   └── 令a=b=1 → 2ⁿ = ΣC(n,i)
├── 经典应用
│   ├── 网格路径计数
│   │   ├── m行n列 → C(m+n, m)
│   │   └── DP递推 = 杨辉三角
│   ├── 组合数预处理
│   └── 概率计算
└── 易错点
    ├── 行列从0开始
    ├── 一维滚动要逆序
    ├── 数据溢出（用long long或取模）
    └── 边界条件C(n,0)=C(n,n)=1

一、📋 考纲要求与考点全景

杨辉三角在八级考纲中属于"组合数学"模块，核心要求包括：

理解杨辉三角的定义，知道第 n 行第 m 个数就是组合数 C(n, m)；
掌握每个数等于它上方两数之和、首尾为 1 的构造规律；
理解杨辉三角与二项式定理 (a+b)ⁿ 展开式系数的对应关系；
能用二维数组递推打印杨辉三角，并用一维滚动数组把空间复杂度从 O(n²) 优化到 O(n)；
会利用杨辉三角求组合数 C(n, m)，并解决路径计数等应用题。

考点	难度	选择/判断频率	编程题频率
杨辉三角的定义与行列对应	⭐	高	中
递推关系 f[i][j]=f[i-1][j-1]+f[i-1][j]	⭐⭐	高	高
边界初始化（首尾为1）	⭐⭐	高	高
滚动数组优化与覆盖顺序	⭐⭐⭐	极高	高
杨辉三角求组合数 C(n,m)	⭐⭐	高	高
二项式定理与系数求和	⭐⭐⭐	高	中
路径计数中的组合数应用	⭐⭐⭐	中	高

二、杨辉三角是什么？🔺

1.1 直观认识

杨辉三角（西方称帕斯卡三角）是一个这样排列的数表。它在我国最早由北宋数学家贾宪用于开方运算，南宋数学家杨辉在《详解九章算法》（1261年）中记载并流传下来，比欧洲帕斯卡的发现早了近四百年：

          1
        1   1
      1   2   1
    1   3   3   1
  1   4   6   4   1
1   5  10  10   5   1

它有三条最基本的构造规律：

每行首尾两个数都是 1；
每个数等于它"肩膀"上两个数之和（上方左数 + 上方右数）；
第 i 行（从 0 开始数）共有 i+1 个数。

1.2 递推关系：用数学语言描述

设 f[i][j] 表示第 i 行、第 j 个数（i、j 均从 0 开始），则：

🔥 高频考点（核心递推式）

f[i][0] = f[i][i] = 1                （边界：每行首尾为1）
f[i][j] = f[i-1][j-1] + f[i-1][j]    （0 < j < i，肩上两数之和）

1.3 与组合数、二项式定理的联系

杨辉三角第 n 行第 m 个数，恰好就是组合数：

f[n][m] = C(n, m)

例如第 4 行是 1 4 6 4 1，正好对应 C(4,0)=1、C(4,1)=4、C(4,2)=6、C(4,3)=4、C(4,4)=1。

为什么递推式成立？因为组合数有帕斯卡恒等式：

C(n, m) = C(n-1, m-1) + C(n-1, m)

组合意义：从 n 个人中选 m 个人，要么选到"特定的某人"（再从剩下 n-1 人中选 m-1 人），要么不选他（从 n-1 人中选 m 人），两类情况相加——这正是第3期加法原理的应用。

而二项式定理告诉我们：

(a + b)ⁿ = C(n,0)aⁿb⁰ + C(n,1)aⁿ⁻¹b¹ + … + C(n,n)a⁰bⁿ

所以 (a+b)ⁿ 展开式的各项系数，就是杨辉三角的第 n 行。例如：

(a+b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴

💡 一张表把三者串起来：杨辉三角是组合数的几何排列，组合数是二项式展开的系数。考试中三者任意给一个，要能立刻想到另外两个。

1.4 三条常用性质速记

性质	数学表达	直观解释
对称性	C(n, m) = C(n, n−m)	三角左右对称，选 m 个 = 去掉 m 个
行和性质	第 n 行之和 = 2ⁿ	令 a=b=1 代入二项式定理
递推性质	C(n, m) = C(n−1, m−1) + C(n−1, m)	每个数等于肩上两数之和

其中对称性在编程时非常实用：计算 C(n, m) 前可先令 m = min(m, n-m)，无论递推还是公式法，循环次数都能减半。

三、二维数组递推实现 🧮

2.1 基本思路

开一个二维数组 f；
逐行递推：每行先把首尾置 1，中间位置由上一行推出；
打印时通过前导空格实现三角形排版。

2.2 例1：打印杨辉三角前 N 行（二维数组版）

题目：输入正整数 N（N ≤ 20），按三角形格式输出杨辉三角的前 N 行。

样例输入：5

样例输出：

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

C++11 代码

cpp

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long f[25][25] = {0};
    for (int i = 0; i < n; i++) {
        f[i][0] = f[i][i] = 1;          // 边界：首尾为1
        for (int j = 1; j < i; j++)     // 中间元素递推
            f[i][j] = f[i-1][j-1] + f[i-1][j];
    }

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n - i; k++)
            cout << "  ";               // 前导空格，形成三角形
        for (int j = 0; j <= i; j++)
            cout << f[i][j] << "   ";
        cout << endl;
    }
    return 0;
}

⚠️ 易错点1：下标从 0 还是从 1 开始？
两种写法都能做对题，但必须前后一致：
下标从 0 开始：第 i 行有 i+1 个数，f[i][j] = C(i,j)，j 的范围是 0..i；
下标从 1 开始：第 i 行有 i 个数，f[i][j] = C(i-1, j-1)。
八级选择题常给一段代码问"f[5][2] 是多少"，数错行号就会丢分。建议统一采用从 0 开始，与组合数 C(n,m) 的下标天然对齐。

复杂度分析：时间 O(N²)，空间 O(N²)。

四、一维滚动数组优化 🔄

3.1 为什么能优化？

观察递推式 f[i][j] = f[i-1][j-1] + f[i-1][j]：计算第 i 行时，只用到第 i-1 行，更早的行再也不需要了。因此可以只用一个一维数组，让新一行的结果覆盖旧一行——这就是"滚动数组"。

版本	空间复杂度	适用场景
二维数组	O(N²)	需要保留整个三角（如多次查询不同 C(n,m)）
一维滚动数组	O(N)	只需当前行 / 只求某一行 / N 很大时

3.2 例2：滚动数组打印前 N 行（O(N) 空间）

C++11 代码

cpp

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long f[25] = {0};
    for (int i = 0; i < n; i++) {
        f[i] = 1;                          // 新行的末尾为1
        for (int j = i - 1; j >= 1; j--)   // ⚠️ 必须从右往左！
            f[j] = f[j] + f[j - 1];
        // f[0] 始终为1，不用动

        for (int k = 0; k < n - i; k++) cout << "  ";
        for (int j = 0; j <= i; j++) cout << f[j] << "   ";
        cout << endl;
    }
    return 0;
}

🔥 高频考点（必考易错点）：滚动数组为什么必须从右往左覆盖？
递推式 f[j] = 旧f[j] + 旧f[j-1]。等号右边两个值都必须是上一行的：
从右往左（j 由大到小）：算 f[j] 时，f[j-1] 还没被本轮动过，存的是旧值 ✅
从左往右（j 由小到大）：算 f[j] 时，f[j-1] 已被覆盖成新一行的值，等于"新数加新数"，整行全错 ❌
这和 0/1 背包一维化后容量必须逆序遍历是同一个道理，八级判断题反复考查。

手动模拟前 3 行（数组初始全 0，f[0] 恒为 1）：

轮次 i	覆盖后 f[0..i]	说明
i=0	`1`	f[0]=1
i=1	`1 1`	f[1]=1，内循环不执行
i=2	`1 2 1`	f[2]=1；j=1：f[1]=f[1]+f[0]=2
i=3	`1 3 3 1`	f[3]=1；j=2：f[2]=1+2=3；j=1：f[1]=2+1=3

五、用杨辉三角求组合数 C(n, m) 🔢

既然 f[n][m] = C(n, m)，求组合数就有了一条"递推不取模也不会遇到除法"的路线，特别适合结果需要取模的场景（阶乘公式涉及除法，取模时要算逆元，超出八级要求）。

4.1 例3：求组合数 C(n, m)（对 10⁹+7 取模）

题目：输入 n、m（0 ≤ m ≤ n ≤ 2000），输出 C(n, m) mod 1000000007。

思路：滚动数组递推到第 n 行，f[m] 即为答案。利用对称性 C(n,m) = C(n,n-m)，可先把 m 取 min(m, n-m) 减少思维负担（递推本身不影响，但公式法很有用）。

C++11 代码（杨辉三角递推法）

cpp

#include <iostream>
#include <algorithm>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n, m;
    cin >> n >> m;
    if (m < 0 || m > n) { cout << 0 << endl; return 0; }

    long long f[2005] = {0};
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = i - 1; j >= 1; j--)
            f[j] = (f[j] + f[j - 1]) % MOD;  // 递推中取模
    }
    cout << f[m] << endl;
    return 0;
}

对比：公式法（不取模时更快）

C(n,m) = n! / (m! · (n-m)!)，边乘边除可保证每步整除，时间 O(m)：

cpp

long long C = 1;
for (int i = 1; i <= m; i++)
    C = C * (n - m + i) / i;   // 先乘后除，始终整除

⚠️ 易错点2：行列对应关系
求 C(5,2) 要递推到第 5 行（i 从 0 数到 5，共 6 行），取第 2 个数，答案是 10。考场上常见错误是循环只写到 i < n，少递推一行。记住：第 n 行 = (a+b)ⁿ 的系数 = C(n, ·)，行号与上标严格对齐。

六、二项式系数求和 ➕

5.1 两个重要结论

令二项式定理中 a、b 取特殊值，立刻得到杨辉三角两行"隐藏性质"：

代入	结论	组合意义
a=1, b=1	C(n,0)+C(n,1)+…+C(n,n) = 2ⁿ	第 n 行所有数之和为 2ⁿ；n 个元素的子集总数
a=1, b=−1	奇数项和 = 偶数项和 = 2ⁿ⁻¹（n≥1）	选奇数个与选偶数个的方案数一样多

🔥 高频考点："杨辉三角第 n 行所有数之和是多少？"——答案 2ⁿ。编程题中可以直接用位运算 1LL << n 或快速幂输出，但用递推把第 n 行累加一遍是最稳妥的验证方式。

5.2 例4：二项式系数求和

题目：输入 n（1 ≤ n ≤ 60），输出三个整数：第 n 行系数之和、奇数位置（j 为奇数）系数之和、偶数位置系数之和，均对 10⁹+7 取模。

样例输入：4（第4行 1 4 6 4 1） 样例输出：16 8 8

C++11 代码

cpp

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n;
    cin >> n;

    long long f[65] = {0};
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = i - 1; j >= 1; j--)
            f[j] = (f[j] + f[j - 1]) % MOD;
    }

    long long total = 0, odd = 0, even = 0;
    for (int j = 0; j <= n; j++) {
        total = (total + f[j]) % MOD;
        if (j % 2 == 1) odd = (odd + f[j]) % MOD;
        else            even = (even + f[j]) % MOD;
    }
    cout << total << " " << odd << " " << even << endl;
    // 验算：total == 2^n，odd == even == 2^(n-1)
    return 0;
}

七、路径计数：组合数的经典应用题 🚶

6.1 模型

在网格中从左上角 A 走到右下角 B，每步只能向右或向下，问有多少条不同路径？

设从 A 到 B 一共要向下走 n 段、向右走 m 段（共 n+m 步），那么任意一条路径都对应"在 n+m 步中选出 n 步向下（其余向右）"的一个方案：

路径总数 = C(n+m, n) = C(n+m, m)

这正是第2期乘法原理/第3期组合的直接应用，而计算交给杨辉三角递推即可。

6.2 例5：网格路径计数

题目：输入 n、m（0 ≤ n, m ≤ 1000），表示从坐标 (0,0) 走到 (n,m)，每步只能向右或向下。求路径条数对 10⁹+7 取模。

样例输入：2 3样例输出：10（C(5,2) = 10）

C++11 代码

cpp

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n, m;
    cin >> n >> m;

    int N = n + m;                 // 需要递推到第 N 行
    long long f[2005] = {0};
    f[0] = 1;
    for (int i = 1; i <= N; i++) {
        f[i] = 1;
        for (int j = i - 1; j >= 1; j--)
            f[j] = (f[j] + f[j - 1]) % MOD;
    }
    cout << f[n] << endl;          // C(n+m, n)
    return 0;
}

💡 变形提醒：若题目规定某些格子"不能走"（障碍），就退化为二维 DP：dp[i][j] = dp[i-1][j] + dp[i][j-1]，障碍格置 0——递推形式和杨辉三角完全同构。这也是八级编程题喜欢的综合考法。

八、高频易错点汇总 ⚡

序号	易错点	正确结论
1	下标从 0 还是 1 开始分不清	从 0 开始时第 i 行有 i+1 个数，f[i][j]=C(i,j)，全题统一
2	求 C(n,m) 只递推到第 n−1 行	必须递推到第 n 行（i 取到 n）
3	滚动数组从左往右覆盖	❌ 必须从右往左，否则 f[j-1] 已是新值
4	忘记首尾边界初始化	每行 f[i][0]=f[i][i]=1（滚动版 f[i]=1，f[0] 恒为1）
5	第 n 行系数和误以为是 2ⁿ⁻¹	第 n 行和为 2ⁿ；奇偶项各为 2ⁿ⁻¹
6	路径数误用 C(n+m, n)·C(n+m, m)	选 n 步向下后路径已确定，答案是 C(n+m, n)
7	取模时用阶乘公式直接除	模意义下除法要用逆元；八级优先用递推法避免除法
8	三角形排版忘记前导空格	第 i 行打印 n−i 个缩进单位，否则输出直角三角

九、备考建议 🏋️

杨辉三角题目的"护城河"不在知识难度，而在手工模拟能力：考场上遇到读程序写结果的选择题，一定要在草稿纸上把滚动数组一行行覆盖出来，特别留意覆盖方向。

必背内容	优先级
递推式 f[i][j]=f[i-1][j-1]+f[i-1][j] 与边界	⭐⭐⭐⭐⭐
滚动数组模板（从右往左）	⭐⭐⭐⭐⭐
f[n][m]=C(n,m)、第 n 行和为 2ⁿ	⭐⭐⭐⭐⭐
路径计数 C(n+m, n)	⭐⭐⭐⭐
二项式定理展开式系数对应	⭐⭐⭐⭐

练习题 4（单选题）

题目： 杨辉三角第 5 行（行号从 0 开始）所有数字的和是多少？（）

A. 10
B. 16
C. 32
D. 64

🔑 点击查看答案与解析

答案： C

解析： 杨辉三角的重要性质：第 n 行所有数字的和 = 2ⁿ

第 5 行的和 = 2⁵ = 32

验证（第5行）：1 + 5 + 10 + 10 + 5 + 1 = 32 ✓

为什么？因为二项式定理：(1+1)ⁿ = ΣC(n,i) = 第n行数字和 = 2ⁿ

选 C。

💡 记忆口诀：杨辉三角第 n 行和 = 2 的 n 次方。

---

练习题 5（判断题）

题目： 杨辉三角中，第 6 行第 2 个数和第 6 行第 4 个数相等。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 杨辉三角左右对称，因为 C(n, m) = C(n, n-m)。

第 6 行第 2 个数 = C(6, 2) 第 6 行第 4 个数 = C(6, 4) = C(6, 6-4) = C(6, 2)

所以两者相等。

验证：

C(6,2) = 6×5/2 = 15
C(6,4) = 6×5×4×3/4×3×2×1 = 15

相等 ✓

💡 选 2 个 = 不选 4 个，所以方案数一样。

---

练习题 6（单选题）

题目： 用一维滚动数组实现杨辉三角时，内层循环应该按什么顺序遍历？（）

A. 从左到右（从小到大）
B. 从右到左（从大到小）
C. 从中间到两边
D. 任意顺序都可以

🔑 点击查看答案与解析

答案： B

解析： 一维滚动数组实现杨辉三角，内层循环必须**从右到左（逆序）**遍历。

原因：杨辉三角的递推式是 f[j] = f[j-1] + f[j]，这里的 f[j-1] 应该是"上一行"的结果。

如果从左到右遍历：f[j-1] 已经被更新过了（变成了当前行的值），就错了
如果从右到左遍历：f[j-1] 还没被更新，还是上一行的值，正确

这和 01 背包一维化要逆序遍历是同一个道理！

选 B。

🔥 高频考点：滚动数组逆序遍历是选择题和代码填空题的常客。

---

练习题 7（单选题）

题目： (1 + x)⁴ 的展开式中 x² 的系数是多少？（）

A. 4
B. 6
C. 8
D. 12

🔑 点击查看答案与解析

答案： B

解析： 二项式定理：(a + b)ⁿ 的展开式中，第 k 项（从 0 开始数）的系数是 C(n, k)。

(1 + x)⁴ 中 x² 的系数 = C(4, 2) = 4×3/2×1 = 6

验证展开： (1+x)⁴ = 1 + 4x + 6x² + 4x³ + x⁴ x² 的系数确实是 6 ✓

选 B。

💡 杨辉三角第 4 行：1 4 6 4 1，正好就是展开式的系数！

---

练习题 8（编程题）

题目： 输入 n，输出杨辉三角的前 n 行。

输入：一个整数 n
输出：n 行，每行数字用空格隔开

样例输入：5
样例输出：

🔑 点击查看答案与解析

答案： 参考代码（二维数组实现）：

cpp

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[25][25] = {0};
    
    for (int i = 0; i < n; i++) {
        a[i][0] = 1;     // 每行第一个是1
        a[i][i] = 1;     // 每行最后一个是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;
}

解析： 杨辉三角生成步骤：

初始化边界：每行第一个和最后一个都是 1
递推中间：每个数 = 它左上方的数 + 正上方的数
逐行生成：从第 0 行到第 n-1 行

💡 一维滚动数组版本（空间优化）：

cpp

int f[25] = {0};
f[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = i; j >= 1; j--)  // 逆序！
        f[j] = f[j-1] + f[j];
    // 输出第i行
}

---

十、📝 实战练习

练习题 1（单选题）

题目： 使用一维滚动数组递推杨辉三角，当 i=4 这一轮覆盖完成后，数组 f[0..4] 的内容是？

A. 1 3 3 1 0
B. 1 4 6 4 1
C. 1 4 5 4 1
D. 1 2 3 4 1

🔑 点击查看答案与解析

答案： B

i=4 时：f[4]=1；j=3：f[3]=旧f[3]+旧f[2]=3+3=6；j=2：f[2]=旧f[2]+旧f[1]=3+3=6；j=1：f[1]=旧f[1]+旧f[0]=3+1=4。因从右往左算，f[j−1] 尚未被覆盖，右侧始终是上一轮 (1,3,3,1) 的旧值，最终得到第4行 1 4 6 4 1。若误从左往右算会得到错误结果。

练习题 2（判断题）

题目： 用一维滚动数组计算杨辉三角时，内层循环 j 从小到大遍历和从大到小遍历都能得到正确结果，因为加法满足交换律。

🔑 点击查看答案与解析

答案： 错误 ❌

加法交换律不解决问题。f[j] = f[j] + f[j-1] 要求右侧是上一行的两个旧值。从小到大遍历时 f[j-1] 已被本轮覆盖为新值，导致"新数加新数"。必须**从大到小（从右往左）**遍历。

练习题 3（编程题）

题目： 题目：输入 n、m（0 ≤ m ≤ n ≤ 1000），输出 C(n, m) 对 1000000007 取模的结果。要求空间复杂度不超过 O(n)。

样例输入：5 2样例输出：10

🔑 点击查看答案与解析

**解析：**即本文例3，滚动数组递推到第 n 行输出 f[m]。时间 O(n²)、空间 O(n)。参考代码见例3。注意边界 m=0 或 m=n 时答案为 1，递推天然成立，无需特判。

十一、📊 考点总结表

考点	重要程度	出题形式	易错点
杨辉三角递推公式	⭐⭐⭐⭐⭐	选择/编程	f[i][j]=f[i-1][j-1]+f[i-1][j]
边界条件	⭐⭐⭐⭐⭐	代码填空/选择	C(n,0)=C(n,n)=1
第n行第m列=C(n,m)	⭐⭐⭐⭐⭐	选择/判断	行列从0开始
对称性 C(n,m)=C(n,n-m)	⭐⭐⭐⭐	选择/判断	左右对称
第n行和=2ⁿ	⭐⭐⭐⭐⭐	选择/判断	二项式定理(1+1)ⁿ
一维滚动数组逆序	⭐⭐⭐⭐⭐	选择/代码填空	从右往左遍历
二项式系数	⭐⭐⭐⭐	选择/计算	(a+b)ⁿ展开系数
网格路径计数	⭐⭐⭐⭐⭐	选择/DP	C(m+n,m)
数据溢出	⭐⭐⭐⭐	编程/判断	用long long或取模
手工模拟滚动数组	⭐⭐⭐⭐⭐	程序阅读题	一行行覆盖，注意方向

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│       杨辉三角 · 必背速记卡                 │
├─────────────────────────────────────────────┤
│  1. 递推式：C(i,j)=C(i-1,j-1)+C(i-1,j)      │
│  2. 边界：C(n,0)=C(n,n)=1                   │
│  3. 第n行第m列 = C(n,m)                     │
│  4. 行列都从0开始数                         │
│  5. 对称性：C(n,m)=C(n,n-m)                 │
│  6. 第n行数字和 = 2^n                       │
│  7. 一维滚动数组：逆序遍历（从右往左）       │
│  8. 滚动数组逆序原因：防止j-1被提前更新     │
│  9. 二项式定理：(a+b)^n系数=杨辉三角第n行   │
│ 10. (1+1)^n = 2^n = 第n行和                │
│ 11. 网格路径（右+下）：C(m+n,m)             │
│ 12. 杨辉三角左右对称                       │
│ 13. 第i行有i+1个数                          │
│ 14. 数据大时用long long或取模              │
│ 15. 杨辉三角 = 组合数表 = DP递推            │
└─────────────────────────────────────────────┘

第4章 杨辉三角 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、📋 考纲要求与考点全景 ​

二、杨辉三角是什么？🔺 ​

1.1 直观认识 ​

1.2 递推关系：用数学语言描述 ​

1.3 与组合数、二项式定理的联系 ​

1.4 三条常用性质速记 ​

三、二维数组递推实现 🧮 ​

2.1 基本思路 ​

2.2 例1：打印杨辉三角前 N 行（二维数组版） ​

C++11 代码 ​

四、一维滚动数组优化 🔄 ​

3.1 为什么能优化？ ​

3.2 例2：滚动数组打印前 N 行（O(N) 空间） ​

C++11 代码 ​

五、用杨辉三角求组合数 C(n, m) 🔢 ​

4.1 例3：求组合数 C(n, m)（对 10⁹+7 取模） ​

C++11 代码（杨辉三角递推法） ​

六、二项式系数求和 ➕ ​

5.1 两个重要结论 ​

5.2 例4：二项式系数求和 ​

C++11 代码 ​

七、路径计数：组合数的经典应用题 🚶 ​

6.1 模型 ​

6.2 例5：网格路径计数 ​

C++11 代码 ​

八、高频易错点汇总 ⚡ ​

九、备考建议 🏋️ ​

练习题 4（单选题） ​

练习题 5（判断题） ​

练习题 6（单选题） ​

练习题 7（单选题） ​

练习题 8（编程题） ​

十、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（判断题） ​

练习题 3（编程题） ​

十一、📊 考点总结表 ​

⭐ 必背速记卡 ​

第4章杨辉三角

🎯 本章学习目标

🗺️ 本章知识图谱

一、📋 考纲要求与考点全景

二、杨辉三角是什么？🔺

1.1 直观认识

1.2 递推关系：用数学语言描述

1.3 与组合数、二项式定理的联系

1.4 三条常用性质速记

三、二维数组递推实现 🧮

2.1 基本思路

2.2 例1：打印杨辉三角前 N 行（二维数组版）

C++11 代码

四、一维滚动数组优化 🔄

3.1 为什么能优化？

3.2 例2：滚动数组打印前 N 行（O(N) 空间）

C++11 代码

五、用杨辉三角求组合数 C(n, m) 🔢

4.1 例3：求组合数 C(n, m)（对 10⁹+7 取模）

C++11 代码（杨辉三角递推法）

六、二项式系数求和 ➕

5.1 两个重要结论

5.2 例4：二项式系数求和

C++11 代码

七、路径计数：组合数的经典应用题 🚶

6.1 模型

6.2 例5：网格路径计数

C++11 代码

八、高频易错点汇总 ⚡

九、备考建议 🏋️

练习题 4（单选题）

练习题 5（判断题）

练习题 6（单选题）

练习题 7（单选题）

练习题 8（编程题）

十、📝 实战练习

练习题 1（单选题）

练习题 2（判断题）

练习题 3（编程题）

十一、📊 考点总结表

⭐ 必背速记卡