解題說明
N-th Tribonacci Number
題目描述：Tribonacci 數列定義為 T(0)=0, T(1)=1, T(2)=1，之後每項等於前三項之和：T(n) = T(n-1) + T(n-2) + T(n-3)。給定 n，求 T(n)。
解題思路：此題是 Fibonacci 的推廣版本。最直覺的方式是動態規劃：從 T(0), T(1), T(2) 出發，逐步計算到 T(n)。由於每一步只依賴前三個值，可以只用三個變數滾動更新，將空間複雜度壓到 O(1)。不需要遞迴或記憶化，迭代版本就是最簡潔且高效的解法。
C++ 解法
複雜度分析
時間複雜度：O(n) — 單層迴圈從 3 到 n，每次 O(1) 計算。
空間複雜度：O(1) — 只使用三個整數變數滾動儲存，不需額外陣列。
虛擬碼
1. Handle base cases: n=0 -> 0, n=1 or n=2 -> 1 2. Initialize a=0, b=1, c=1 3. For i from 3 to n: a. next = a + b + c b. a = b, b = c, c = next 4. Return c
其他解法
遞迴 + 記憶化：自頂向下遞迴，用 map 或陣列快取已計算的值，避免重複計算。時間複雜度同為 O(n)，但有遞迴呼叫開銷和 O(n) 額外空間。
矩陣快速冪：將三項遞推關係寫成 3×3 矩陣乘法，用快速冪在 O(log n) 時間求解。在 n 極大（如 10^18）時才有必要，本題 n ≤ 37 無需此法。
延伸思考
- 如何用矩陣快速冪在 O(log n) 內求 T(n)？
- 若改為 k-bonacci（前 k 項之和），如何泛化此解法？
- Tribonacci 數列的比值 T(n+1)/T(n) 收斂至什麼值（Tribonacci 常數）？