LeetCode 118：生成帕斯卡三角形（逐行構建）

題目描述

給定行數 numRows，生成帕斯卡三角形的前 numRows 行。每行首尾為 1，中間元素等於上一行對應兩元素之和。

逐行構建算法

初始化結果為空。對於每一行 i（0-indexed），創建長度 i+1 的向量，首尾置 1，中間元素由上一行 res[i-1][j-1] + res[i-1][j] 計算。

代碼實現 (C++)

class Solution {
public:
    vector> generate(int numRows) {
        vector> res;
        for (int i = 0; i < numRows; ++i) {
            vector row(i+1, 1);
            for (int j = 1; j < i; ++j) {
                row[j] = res[i-1][j-1] + res[i-1][j];
            }
            res.push_back(row);
        }
        return res;
    }
};

複雜度

• 時間：O(numRows^2)
• 空間：O(numRows^2)