解題說明
Pascal's Triangle II
題目描述：給定整數 rowIndex（0-indexed），回傳帕斯卡三角形的第 rowIndex 列，並要求只使用 O(rowIndex) 的額外空間。
解題思路：本題的關鍵限制是空間只能為 O(k)（k = rowIndex），因此不能儲存整個三角形，只能維護單一列並原地更新。
核心技巧：從右往左更新
若從左往右更新，row[j] = row[j-1] + row[j] 時，row[j-1] 已被本輪覆寫，導致錯誤。若從右往左更新，計算 row[j] 時所需的 row[j-1] 尚未被修改，仍代表上一列的值，可正確計算。
步驟：
- 初始化
row = [1]（第 0 列）。 - 對每一輪
i（從 1 到rowIndex）：- 在陣列尾端新增一個 1（擴展列長度）。
- 從右往左更新中間元素：
row[j] += row[j-1]（j 從i-1到 1）。
- 回傳
row。
C++ 解法
複雜度分析
時間複雜度：O(rowIndex²) — 共執行 rowIndex 輪，第 i 輪需更新 i-1 個元素，總操作數為 0 + 1 + ... + (rowIndex-1) = O(rowIndex²)。若使用組合數公式，時間複雜度為 O(rowIndex)。
空間複雜度：O(rowIndex) — 僅使用一個長度為 rowIndex+1 的陣列，符合題目要求的空間限制。
虛擬碼
1. Initialize row = [1].
2. For i from 1 to rowIndex:
a. Append 1 to end of row (row now has i+1 elements).
b. For j from i-1 down to 1:
- row[j] = row[j] + row[j-1]
(right-to-left update preserves previous-row values)
3. Return row.
Alternative (combination formula):
1. Initialize row of size rowIndex+1; set row[0] = 1.
2. For k from 1 to rowIndex:
- row[k] = row[k-1] * (rowIndex - k + 1) / k
3. Return row.其他解法
方法一：組合數公式 C(n, k)
- 第
rowIndex列的第k個元素（0-indexed）等於 C(rowIndex, k)。利用遞推公式C(n, k) = C(n, k-1) * (n - k + 1) / k可從左至右 O(1) 空間逐個計算每個元素，無需依賴上一列資料。注意中間乘法可能溢位，需使用long long暫存。 - 時間複雜度：O(rowIndex)，空間複雜度：O(rowIndex)（僅輸出陣列）
方法二：完整建構帕斯卡三角形（空間換時間）
- 逐列建構所有列並儲存，最後回傳第
rowIndex列。這等同於 LeetCode 118 的解法，直觀但使用 O(rowIndex²) 空間，不符合本題的空間限制要求，適合作為理解題意的初始解法。 - 時間複雜度：O(rowIndex²)，空間複雜度：O(rowIndex²)
延伸思考
- 使用組合數公式 C(n, k) 計算時，為何中間步驟需要使用
long long而不是int？在哪個 rowIndex 值時int會溢位？ - 從右往左更新陣列是一種常見的「滾動陣列」技巧，你還能想到哪些動態規劃問題使用了相同的技巧（例如 0/1 背包問題）？
- 若 rowIndex 超過 30，帕斯卡三角形的元素值會超過 32 位元整數範圍。若題目要求所有元素對 10^9+7 取模後回傳，你的解法需要如何修改？