题解 | #杨辉三角#

题目链接

杨辉三角

题目描述

杨辉三角形，又称帕斯卡三角形，是一个经典的数学结构。它有如下性质：

第 n 行有 n 个元素（从第1行算起）。
每行的第一个和最后一个元素都是 1。
对于其他元素，Triangle[i][j] = Triangle[i-1][j-1] + Triangle[i-1][j] (使用0-based索引时)。即，每个数等于它上方两数之和。

给定正整数 n，请输出杨辉三角形的前 n 行。

输入描述:

在一行输入一个整数 n (1 <= n <= 30)。

输出描述:

输出杨辉三角形的前 n 行。
每行数字之间用一个空格分隔，行末无多余空格。

示例:

输入: 4
输出:
```
1
1 1
1 2 1
1 3 3 1
```

解题思路

解决这个问题的最直接方法是模拟杨辉三角的生成过程。我们可以利用其递推的性质，逐行构建整个三角形。这是一种典型的动态规划思想。

数据结构: 我们可以使用一个二维数组（或列表的列表）来存储整个杨辉三角形。设其为 triangle。由于第 i 行有 i+1 个元素（采用0-based索引），我们可以创建一个 n x n 的数组或一个"锯齿"数组来节省空间。
构建三角形:
- 我们从第 0 行开始，一直构建到第 n-1 行。
- 对于每一行 i（从 0 到 n-1）：
  - 该行将有 i+1 个元素。
  - 边界条件: 根据定义，该行的第一个元素 triangle[i][0] 和最后一个元素 triangle[i][i] 都是 1。
  - 递推关系: 对于行内的其他元素 triangle[i][j]（其中 1 <= j < i），它的值等于它正上方的元素 triangle[i-1][j] 与左上方的元素 triangle[i-1][j-1] 之和。
  - 我们可以用一个内层循环来计算这些中间值。
打印结果:
- 当整个二维数组 triangle 被填充完毕后，它就包含了杨辉三角的前 n 行。
- 最后，我们遍历这个二维数组，逐行打印。
- 注意控制输出格式，确保每个数字间有一个空格，且行末没有多余的空格。

算法步骤概览:

读入 n。
创建 n 行的二维数组 triangle。
for i from 0 to n-1:
- 将第 i 行的大小设置为 i+1。
- 设置 triangle[i][0] = 1 和 triangle[i][i] = 1。
- for j from 1 to i-1:
  - triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]。
遍历 triangle，按格式打印每一行。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 1. 构建杨辉三角
    vector<vector<int>> triangle(n);
    for (int i = 0; i < n; ++i) {
        triangle[i].resize(i + 1); // 第 i 行有 i+1 个元素
        triangle[i][0] = 1;        // 行首为 1
        triangle[i][i] = 1;        // 行尾为 1
        
        for (int j = 1; j < i; ++j) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    
    // 2. 打印结果
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < triangle[i].size(); ++j) {
            cout << triangle[i][j] << (j == triangle[i].size() - 1 ? "" : " ");
        }
        cout << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 1. 构建杨辉三角 (使用锯齿数组)
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];
            triangle[i][0] = 1;
            triangle[i][i] = 1;
            
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
        }
        
        // 2. 打印结果
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                System.out.print(triangle[i][j]);
                if (j < triangle[i].length - 1) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
}

n = int(input())

# 1. 构建杨辉三角
triangle = []
for i in range(n):
    # 用 1 初始化当前行
    row = [1] * (i + 1)
    # 计算行内非 1 的元素
    if i >= 2: # 前两行 (i=0, i=1) 不需要计算
        prev_row = triangle[i-1]
        for j in range(1, i):
            row[j] = prev_row[j-1] + prev_row[j]
    triangle.append(row)

# 2. 打印结果
for row in triangle:
    # 将行内所有元素转为字符串再用空格连接，可完美处理行末空格
    print(' '.join(map(str, row)))

算法及复杂度

算法: 动态规划。
时间复杂度: $\mathcal{O}(N^2)$ 。我们需要计算的元素总数是 $1 + 2 + \dots + N = \frac{N(N+1)}{2}$ ，所以填充整个三角形的时间复杂度为 $\mathcal{O}(N^2)$ 。
空间复杂度: $\mathcal{O}(N^2)$ 。我们需要一个二维数组来存储整个三角形，空间消耗与元素总数成正比。