動態規劃 Lecture 1X: 費氏數列

從前一節的爬樓梯問題中，若我們將 $n=0, 1, 2, 3, \ldots$ 的前幾項答案印出來，我們可以發現數列長得像這樣：$1, 1, 2, 3, 5, 8, \ldots$。這個數列有個特別的名稱，它叫做費氏數列。（又稱為費波那契數列）

我們正式地給出費氏數列 $\{F_n\}_{n=0}^\infty$ 的定義如下：

$$\left\{\begin{aligned}& F_0=F_1=1 & \\ & F_{n+1} = F_n + F_{n-1} & \forall n \ge 2\end{aligned} \right.$$

快速計算費氏數列可以利用矩陣運算，即把費氏數列的計算表示成矩陣的樣子：

$$\begin{bmatrix}1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix}F_n\\ F_{n-1}\end{bmatrix} = \begin{bmatrix} F_{n+1} \\ F_{n}\end{bmatrix}$$

因此我們能夠在 $O(\log n)$ 的時間利用矩陣的快速冪計算出 $F_n$ 的值。

$$\begin{bmatrix} F_{n} \\ F_{n-1}\end{bmatrix} =\begin{bmatrix}1 & 1 \\ 1 & 0 \end{bmatrix}^n\begin{bmatrix}1\\ 0\end{bmatrix}$$

由於其遞迴的定義方式，有許多比賽曾經利用相同的概念出題。