解题思路

杨辉三角是这样的：

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

规律：

1. 每行的第一个数都是 1
2. 其他每个数 = 上一行同位置的数 + 上一行左边那个数

比如第 5 行（1 4 6 4 1）：

• 第一个 1
• 4 = 上一行(1 3 3 1)的第 2 个数 3 + 第 1 个数 1
• 6 = 3 + 3
• 4 = 3 + 1
• 最后一个 1（上一行越界位置算 0，0+1=1）

怎么实现？

1. 用二维数组 a 存杨辉三角
2. 双重循环：第 i 行有 i+1 个数
3. j==0 时设 1，其他位置 a[i][j] = a[i-1][j] + a[i-1][j-1]
4. 每行最后一个数会自动变成 1（因为上一行越界处是 0）

参考代码

#include <iostream>
using namespace std;

int main() {
    int n, a[100][100];
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                a[i][j] = 1;  // 每行第一个数是 1
            } else {
                a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，构造和输出各一遍
• 空间复杂度：O(N²)，二维数组存三角