leetcode118：杨辉三角

题目链接

leetcode

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

C++ 代码

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

/*
    从上向下，依次计算每一行。
    对于每一行，先把 1 放在首尾两个位置，
    然后计算中间的数：f[i][j] = f[i-1][j-1] + f[i-1][j]

    时间复杂度：O(n^2)
        假设行数为 n，
        计算 n(n+1)/2 个数字，计算每个数字的时间复杂度是 O(1)，
        总的时间复杂度是 O(n^2)。
    空间复杂度：O(n^2)
*/
class Solution_1 {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> f(numRows);

        for (int i = 0; i < numRows; i++) {
            f[i].resize(i+1);
            // 初始化
            f[i][0] = f[i][i] = 1;
            // 状态计算
            for (int j = 1; j < i; j++) {
                f[i][j] = f[i-1][j-1] + f[i-1][j];
            }
        }

        return f;
    }
};

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<int> rows_cases = { 5, 1 };

    for (int i = 0; i < rows_cases.size(); i++) {
        int rows = rows_cases[i];
        vector<vector<int>> result = solution.generate(rows);

        cout << "Input: numRows = " << rows << endl;
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}