解题思路

杨辉三角是一个很有规律的三角形数字表：

• 第 i 行一共有 i 个数；
• 每行的第一个数和最后一个数都是 1；
• 中间第 j 个数 = 上一行第 j-1 个数 + 上一行第 j 个数。

我们用二维数组 a[i][j] 存第 i 行第 j 个数（从 1 开始编号）。

从第 1 行开始，一行一行地“造”：

1. 先固定 a[i][1] = 1 和 a[i][i] = 1，也就是这一行的头和尾；
2. 再用上面的公式，把中间的每个数算出来；
3. 最后逐行输出，同一行里数之间用空格隔开。

参考代码

// P4441 杨辉三角：用二维数组一行一行地算出每个位置的数
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;               // 要输出 n 行杨辉三角
    int a[105][105] = {0};  // a[i][j] 存第 i 行第 j 个数
    // 一行一行生成杨辉三角
    for (int i = 1; i <= n; i++) {
        a[i][1] = 1;        // 每行的第一个数是 1
        a[i][i] = 1;        // 每行的最后一个数是 1
        // 中间的数 = 上一行同一列的数 + 上一行前一列的数
        for (int j = 2; j < i; j++) {
            a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
        }
    }
    // 逐行输出，同一行的数之间用空格隔开
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (j > 1) cout << " ";
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

复杂度分析

设输出 n 行杨辉三角。

• 时间：一共要算出 1+2+...+n = n(n+1)/2 个数，每个数只算一次，所以时间复杂度是 O(n^2)。
• 空间：二维数组存了整个三角形，空间复杂度是 O(n^2)。