杨辉三角-递归实现

Posted on

题目描述

题目链接：N诺/DreamJudge 1392

输入 n 值，使用递归函数求杨辉三角形中各个位置上的值，输出 n 行杨辉三角。

  • 输入：一个大于等于 2 的整数 n
  • 输出：对应 n 行的杨辉三角形
  • 多组测试数据

核心思路

杨辉三角的定义本身就是递归的：

边界条件： 或 时值为 1。

直接用这个递推式写递归很简单，但存在大量重复计算——同一个 会被反复调用，时间复杂度指数级。记忆化搜索用一个二维数组把算过的值存下来，每个 只算一次。

版本一：朴素递归（无记忆化）

递归函数

1
2
3
4
5
6
int yanghui(int i, int j) {
    if (j == 0 || j == i) {
        return 1;
    }
    return yanghui(i - 1, j) + yanghui(i - 1, j - 1);
}

逻辑直接对应杨辉三角的递推公式：

  • → 边界返回 1
  • 否则递归计算左上和正上两个值相加

输出部分

输出时注意：i=0 的那行只有一个 1，跳过不输出（因为题目输出样例从第二行开始）。

1
2
3
4
5
6
7
for (int i = 0; i < t; i++) {
    for (int j = 0; j <= i; j++) {
        if (i == 0) break;           // 跳过第一行
        cout << yanghui(i, j) << " ";
    }
    if (i != 0) cout << endl;
}

⚠️ 复杂度问题

朴素递归的时间复杂度是 。以 n=6 为例，yanghui(5,2) 会被调用多次：

1
2
3
4
yanghui(5,2)
├── yanghui(4,2) → yanghui(3,2) → ...
│   └── yanghui(4,1) → yanghui(3,1) → ...
└── yanghui(4,1) → yanghui(3,1) → ...  ← 重复计算！

n 稍大就超时。

版本二：记忆化搜索

核心改动

加一个 vector<vector<int>> memo，初始化为 -1。每次递归前先查表：

1
2
3
4
5
6
7
8
9
10
int yanghui(int i, int j, vector<vector<int>>& memo) {
    if (j == 0 || j == i) {
        return 1;
    }
    if (memo[i][j] != -1) {      // ⚠️ 查表：已经算过就直接返回
        return memo[i][j];
    }
    memo[i][j] = yanghui(i - 1, j - 1, memo) + yanghui(i - 1, j, memo);
    return memo[i][j];
}

时间复杂度降到 ，每个 只算一次。

⚠️ 关键细节

  1. memo 用 -1 初始化，因为杨辉三角的值都是正数，-1 表示”没算过”。
  2. memo 的大小是 n×n，足够存下整个三角形。
  3. memo 要传引用 vector<vector<int>>& memo，否则每次递归都拷贝，记忆化就白写了。

完整调用

1
2
3
4
5
6
7
8
9
10
while (cin >> t) {
    vector<vector<int>> memo(t, vector<int>(t, -1));
    for (int i = 0; i < t; i++) {
        for (int j = 0; j <= i; j++) {
            if (i == 0) break;
            cout << yanghui(i, j, memo) << " ";
        }
        if (i != 0) cout << endl;
    }
}

⚠️ 常见坑点

  1. 第一个版本会超时 — 考试题目的 n 不会太大（通常 n≤20），朴素递归勉强能过，但机试中一旦 n 到 30 就直接 TLE。建议直接用记忆化。
  2. memo 忘了传引用 — 编译能过，但记忆化完全没生效，等于白写。
  3. 输出格式 — 输出样例从第二行开始（1 1），别多输出第一行那个孤零零的 1。

完整代码模板

版本一：朴素递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int yanghui(int i, int j) {
    if (j == 0 || j == i) {
        return 1;
    }
    return yanghui(i - 1, j) + yanghui(i - 1, j - 1);
}

int main() {
    int t;
    while (cin >> t) {
        for (int i = 0; i < t; i++) {
            for (int j = 0; j <= i; j++) {
                if (i == 0) break;
                cout << yanghui(i, j) << " ";
            }
            if (i != 0) {
                cout << endl;
            }
        }
    }
}

版本二：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

int yanghui(int i, int j, vector<vector<int>>& memo) {
    if (j == 0 || j == i) {
        return 1;
    }
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    memo[i][j] = yanghui(i - 1, j - 1, memo) + yanghui(i - 1, j, memo);
    return memo[i][j];
}

int main() {
    int t;
    while (cin >> t) {
        vector<vector<int>> memo(t, vector<int>(t, -1));
        for (int i = 0; i < t; i++) {
            for (int j = 0; j <= i; j++) {
                if (i == 0) break;
                cout << yanghui(i, j, memo) << " ";
            }
            if (i != 0) {
                cout << endl;
            }
        }
    }
}

总结

要点 说明
递推公式
边界 或 时返回 1
朴素递归复杂度 ，大量重复计算
记忆化复杂度 ，空间
关键细节 memo 传引用、初始化为 -1、跳过第一行输出