解題說明
Pascal's Triangle
題目描述：給定整數 numRows，產生帕斯卡三角形的前 numRows 列並回傳。帕斯卡三角形的規律是：每列的首尾元素為 1，中間的每個元素等於上一列中正上方兩個元素之和。
解題思路：逐列建構，利用前一列的資料計算當前列。
具體步驟：
- 初始化結果陣列
triangle。 - 對每一列
i（從 0 到numRows - 1）：- 建立一個長度為
i + 1的列，首尾元素設為 1。 - 對中間每個位置
j（從 1 到i - 1），設row[j] = triangle[i-1][j-1] + triangle[i-1][j]。 - 將此列加入
triangle。
- 建立一個長度為
- 回傳
triangle。
這是一個簡單的動態規劃問題：每個元素的值由前一列兩個相鄰元素決定，狀態轉移明確。
C++ 解法
複雜度分析
時間複雜度：O(numRows²) — 第 i 列（0-indexed）有 i+1 個元素，總元素數為 1 + 2 + ... + numRows = numRows*(numRows+1)/2，故整體為 O(numRows²)。
空間複雜度：O(numRows²) — 輸出陣列本身儲存所有元素，若不計算輸出空間則額外空間為 O(1)（僅需儲存當前列）。
虛擬碼
1. Initialize triangle as an empty list.
2. For i from 0 to numRows - 1:
a. Create row of size (i + 1) filled with 1s.
b. For j from 1 to i - 1:
- row[j] = triangle[i-1][j-1] + triangle[i-1][j]
c. Append row to triangle.
3. Return triangle.其他解法
方法一：利用組合數公式直接計算
- 帕斯卡三角形第
i列（0-indexed）的第j個元素恰好是組合數 C(i, j)。可直接以公式C(i, j) = C(i, j-1) * (i - j + 1) / j逐一計算每個元素，無需參考上一列。 - 優點：每個元素獨立計算，不需儲存整個三角形即可計算任意位置。
- 時間複雜度：O(numRows²)，空間複雜度：O(1)（不計輸出）
方法二：滾動陣列（單列原地更新）
- 若只需要最終結果而不在意中間列，可以維護單一列並從右至左更新，避免建立多餘的中間陣列。但本題要求回傳所有列，因此此方法較適用於「只求第 k 列」的變形題（LeetCode 119）。
- 時間複雜度：O(numRows²)，空間複雜度：O(numRows)（不計輸出）
延伸思考
- 若只需要帕斯卡三角形的第 k 列（0-indexed），能否在 O(k) 的空間內完成，而不儲存整個三角形？（提示：參考 LeetCode 119）
- 帕斯卡三角形與二項式定理有何關聯？第 n 列的元素和為多少？
- 如果 numRows 非常大（例如 10000），整數溢位會是問題嗎？應如何處理大數運算？