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


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

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

$assume\ n=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 秒**的執行時間。