Dynamic Programming, DP 動態規劃（Python Version）

by Gandolfreddy

出發點

請參考以下程式碼。

def fibo(n):
    if n <= 1:
        return n
    return fibo(n-1)+fibo(n-2)


n = 45
for i in range(n+1):
    print(fibo(i), end=' ')
print()

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

$$\{\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$），則執行時間如下圖所示，以下實驗環境為 Windows 10 Professional, Python 3.7.9。

其中 Minutes、Seconds 與 Milliseconds 欄位可大略代表實際程式所花費時間（此部份會因電腦效能而有些許差異），欲找出費波納契數列的第 45 項，就花費了約 17 分鐘 47.646 秒的執行時間。

探究原因

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

$assumen=5$

於上圖中，可見到有重複的函式呼叫

$fibo(3)$、

$fibo(2)$、

$fibo(1)$、

$fibo(0)$ 出現，進而在計算過程中，造成不必要的時間浪費。

改進方式

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

例如上述過程中，可以看到

$fibo(3)$、

$fibo(2)$、

$fibo(1)$、

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

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

f = [0 for i in range(100)]

def fibo(n):
    if f[n]:
        return f[n]
    if n <= 1:
        return n
    f[n] = fibo(n-1) + fibo(n-2)
    return f[n]


n = 45
for i in range(n+1):
    print(fibo(i), end=' ')
print()

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

下圖為引入動態規劃的程式碼，執行時間測量結果，以下實驗環境為 Windows 10 Professional, Python 3.7.9。

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