# Dynamic Programming, DP 動態規劃
by Gandolfreddy

## 出發點
請參考以下程式碼。

# include <bits/stdc++.h>
using namespace std;

int fibo(int n) {
    if (n <= 1)
        return n;
    return fibo(n-1)+fibo(n-2);
}

int main() {
    int n;
    
    n = 45;
    for (int i=0; i<=n; i++)
        cout << fibo(i) << " ";
    cout << endl;

    return 0;
}

此程式碼即依***費波納契數列***定義實作。

\begin{cases}
f(n)=n , & \text{if $n$} \le 1 \\
f(n)=f(n-1)+f(n-2), & \text{if $n$} \gt 1
\end{cases}

而此實作方式為**遞迴**，可以藉由修改 $n$ 值，觀察程式結果的輸出時間。

若以上方的 $n=45$ 表示，則代表我們想要找出費波納契數列的第 45 項（假設首項 $a_0=0$），則執行時間如下圖所示，以下實驗環境為 ***Ubuntu 20.04, gcc 9.3.0***。


其中 ***real*** 欄位代表實際程式所花費時間（此部份會因電腦效能而有些許差異），欲找出費波納契數列的第 45 項，就花費了 21.249 秒的執行時間。

## 探究原因
由於上述程式是以遞迴方式實作費波納契數列，所以在分析程式行為時，可開展出以下樹狀圖。

$assume\ n=5$

於上圖中，可見到有重複的函式呼叫 $fibo(3)$、$fibo(2)$、$fibo(1)$、$fibo(0)$ 出現，進而在計算過程中，造成不必要的時間浪費。

## 改進方式
此時引入***動態規劃***（dynamic programming）的觀念，將原本會重複函式呼叫的部份最佳化，其概念為，在計算數列的過程中，將已經計算過的結果先行儲存，待下次又遇到重複的函式呼叫運算後，就可以直接取得原先儲存的計算數值。

例如上述過程中，可以看到 $fibo(3)$、$fibo(2)$、$fibo(1)$、$fibo(0)$ 都有重複出現的狀況，則最佳化的方向，即是將第一次計算過上述函式呼叫的結果，先儲存起來，待後續又遇到重複呼叫時，先檢查是否已經有計算過的數值可供取用，若有則可直接省去該次計算時間，若無則再進行函式呼叫，計算該數值。

以下為引入動態規劃的程式碼

# include <bits/stdc++.h>
using namespace std;

int f[100] = {0};

int fibo(int n) {
    if (f[n]) 
        return f[n];
    if (n <= 1) 
        return n;
    f[n] = fibo(n-1) + fibo(n-2);
    return f[n];
}

int main() {
    int n;

    n = 45;
    for (int i=0; i<=n; i++)
        cout << fibo(i) << " ";
    cout << endl;

    return 0;
}

可以在上方程式碼中看到，在此使用了***陣列 f***，記錄下每次遞迴中，函式呼叫的結果，所以在下次呼叫該函式時，就會先檢查在該陣列中是否已經存有計算結果，若是有則直接回傳該值，若無則再進行計算，並於計算完成後，再存入該陣列中。

下圖為引入動態規劃的程式碼，執行時間測量結果，以下實驗環境為 ***Ubuntu 20.04, gcc 9.3.0***。


其中 ***real*** 欄位代表實際程式所花費時間（此部份會因電腦效能而有些許差異），欲找出費波納契數列的第 45 項，藉由引入動態規劃法最佳化後，花費時間便降低至 0.016 秒的執行時間。