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{array}{ll}f(n)=n,& \text{if }n\le 1\\ f(n)=f(n-1)+f(n-2),& \text{if }n>1\end{array}$$

而此實作方式為遞迴，可以藉由修改

$n$ 值，觀察程式結果的輸出時間。

若以上方的

$n=45$ 表示，則代表我們想要找出費波納契數列的第 45 項（假設首項

$a_0=0$），則執行時間如下圖所示，以下實驗環境為 Ubuntu 20.04, gcc 9.3.0。

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

探究原因

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

$assumen=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 秒的執行時間。