解題說明
Fibonacci Number
題目描述：費氏數列定義為 F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)（n >= 2）。給定 n，回傳 F(n)。
解題思路：迭代 DP（最優）：只需保存前兩個值 prev 和 curr，每次更新 [prev, curr] = [curr, prev+curr]，只需 O(1) 空間。相較於天真遞迴（O(2ⁿ) 時間），或記憶化遞迴（O(n) 時間 + O(n) 空間），迭代 DP 在時間 O(n)、空間 O(1) 上均最優。進階：矩陣快速冪可達 O(log n)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 單次迴圈從 2 跑到 n。
空間複雜度：O(1) — 只使用 prev、curr 兩個變數，不需陣列。
虛擬碼
1. If n <= 1, return n 2. Set prev = 0, curr = 1 3. For i from 2 to n: a. next = prev + curr b. prev = curr c. curr = next 4. Return curr
其他解法
記憶化遞迴：建立 memo 陣列，fib(n) = memo[n] 若已計算；否則遞迴計算並存入。時間 O(n)，空間 O(n)。
天真遞迴：直接 return fib(n-1) + fib(n-2)，時間 O(2ⁿ)，大 n 下極慢，僅適合理解遞迴概念。
矩陣快速冪：利用 [[1,1],[1,0]]^n 的矩陣冪計算，時間 O(log n)，適合極大 n（不過此題 n <= 30，差異不大）。
數學公式（黃金比例）：F(n) = round(φⁿ / √5)，φ = (1+√5)/2。常數時間，但浮點誤差在大 n 時可能出問題。
延伸思考
- 如何用矩陣快速冪將時間複雜度優化至 O(log n)？
- 費氏數列的第 n 項對 10^9+7 取模應如何計算（避免整數溢位）？
- 費氏數列有哪些有趣的數學性質？（如 Cassini 恆等式、與黃金比例的關係）