費波那契算是經典的遞迴問題，其定義為

F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*）

也就是在第二項以後，所有的值為前兩項的相加．

我們利用這個簡單的問題，來演練一次動態規劃的基礎．

暴力列舉

在一開始，我們先將數學的描述，轉換成程式碼

fun fibonacci(n:Int):Int  {
    return when (n) {
        0 -> {0}
        1 -> {1}
        else -> {
            fibonacci(n-1)+fibonacci(n-2)
        }
    }
}

雖然程式碼很簡單，但是實際在執行時沒有效率，例如，要解決n = 30時的問題，就要先算出n = 29 與 n =28的問題解答，而要計算出 n = 29又需要計算 n =28 與 n = 27…

計算一下時間複雜度

遞迴演算法的複雜度，等於 子問題個數*解決子問題的時間

以這個範例來說，子問題的個數，就等於遞迴樹的節點數目，而這個二元樹的節點數是指數級別，所以其為2^n

而解決子問題的時間，由於這個問題只有加法計算，所以是O(1)

兩者相乘．時間複雜度為O(2^n)

所以如果直接執行上面的程式碼，Kotlin真的會一步一步去計算，那有沒有什麼方法可以減少這個花費的時間呢

回去觀察地遞迴樹，可以看到有大量重複的問題，比如説f(28)，f(29)在上面的圖都計算了兩次(可以看到塗了相同的顏色)，但是照著上面的程式碼執行，這些都會重複計算．並且f(28)底下還有一大顆樹．每次重新計算就會花費大量的資源．但是這個問題其實我們可能已經算過了．

這就是動態規劃的第一個特徵，重疊子問題
明天我們會針對這個問題進行調整