動態規劃 DP

動態規劃 (Dynamic Programming)，簡稱DP

屬於 Divide-and-conquer 的延伸，和 Divide-and-conquer 同樣是藉由 combining the solutions to subproblems。

Dynamic Programming 主要可以將原問題分解為相較簡單的子問題，再通過子問題的解求出複雜問題的方法。

其核心可以說是 記憶化儲存，每當子問題的答案被算出來時，同時將答案儲存在記憶體中，以便下次需要時可以直接透過查表的方式得出解，並從而減少計算量。

以著名的 Fibonacci 為例

Fibonacci Number

簡單的說就是 從第一次等於0，第二次等於1開始，下一個數字等於前兩個數字的相加，以此類推…

所以得出函式 F(n) = F(n-1) + F(n-2)

Recursion

如果用遞迴來寫的話，Function 會像這樣：

1
int Fib(int n){
2
    if(n < 2) return n;
3
    return Fib(n-1) + Fib(n-2);
4
}
5
int main(){
6
    cout << Fib(n) << endl;
7
    return 0;
8
}

雖然在演算法設計上十分直覺，但執行效率不佳，以 n = 5 為例的話 Recursion Tree 畫出來會長這樣：

其時間複雜度 T(n) = O(2^n)，可以發現用遞迴解容易產生多個 overlapping subproblem，光 F(2) 就被呼叫了3次，如果 n 更大的話呢？是否會消耗大量的計算時間？

Dynamic Programming

如果換用 Dynamic Programming 的話，有兩種作法：

• Top-down：Recursion，執行由上到下，較慢，可能有深層遞迴
• Bottom-up：for loop，執行由下到上，較快，有漏掉 subproblems 沒解決的可能

但通常到最後多數情況都會使用 Bottom-up 作法比較多

Bottom-up：

1
long long Fib(long long n){
2
    long long D[n+1];
3
    D[0] = 0;
4
    D[1] = 1;
5
    for(int i=2; i < n+1; i++){
6
        D[i] = D[i-1] + D[i-2];
7
    }
8
    return D[n];
9
}
10
int main(){
11
    cout << Fib(n) << endl;
12
    return 0;
13
}

透過 D[n] 將所有的 subproblems 儲存，當再次碰到重複的 subproblems 就可以透過先前儲存的答案查表得出。

所以其實有點像是用空間換取時間的概念，時間複雜度為 T(n) = O(n)。

跟遞迴的 O(2^n) 效率是差很多的，但在讀寫上遞迴就是比較直覺，但換來的就是效率差，還有除錯的時候會很頭痛，要一直追遞迴…

總結

前面講到 Dynamic Programming 算是 Divide-and-conquer 的延伸，也具有相同的概念。

至於使用時機：

• Divide-and-conquer：independent or disjoint subproblems
• Dynamic Programming：overlapping subproblems

當一個問題具有 optimal substructure 性質時，或許以遞迴的方式可以得出結果，但易產生許多 overlapping subproblems。

以 bottom-up 方式解開所有 subproblems 並儲存，以便建構出原問題之解，就是 Dynamic Programming。

參考來源

費波那契數 - 維基百科

以上皆為自己整理的筆記，僅供參考與複習使用。