<style>
.red{
color:red
}
.blue{
color:blue
}
.green{
color:green
}

</style>
## :speech_balloon: 介紹
Dynamic Programming動態規劃用於解決<span class="blue">**最佳化問題(optimization problems)**</span>常用的演算法之一，透過將大問題不斷<span class="blue">**分割為相關子問題**</span>，並<span class="blue">**紀錄子問題最佳解**</span>回推原始問題的optimal solution即具有<span class="blue">**全域解**</span>的特性。

:::success
:bell: 基本上沒有硬性的先備知識，Dynamic Programming為一種解題方法與思想，可直接閱讀
:::
* 先備知識(建議)
* 基本演算法
* 資料結構

* 文章分類 (參考)
* 難度：★★★
* 重要程度：★★★
* 適合閱讀的人
* 打算刷題
* 增進自身程式能力
:::warning
:heavy_exclamation_mark:本篇先注重在初步理解Dynamic Programming解題思維，故未包含嚴謹的定義與證明
:::
## :book: 觀念
---
### **一、** Dynamic Programming 與 Divide-and-conquer 之差異

Dynamic Programming與Divide-and-conquer兩者概念相似，皆是將大問題分解成小問題再組合成原問題的解，但兩者仍有區別。

* ### Dynamic Programming
#### 將問題分割為<span class="blue">互有連貫性的子問題</span>，以Fibonacci為例

\begin{align}
&F(n)=\;\left\{
\begin{matrix}
F(0)=0\\
F(1)=1\\
F(n) = F(n-1) + F(n-2)\; \text{, n} \in \mathbb N \cap \text{n>1}\\
\end{matrix}
\right.\\
\end{align}
>若要求得F(4)則需將問題分解為F(3)、F(2)，其中F(3)與F(2)並<span class="red">**非獨立**</span>子問題，F(3)必須知道F(2)與F(1)的值才<span class="red">**可計算**</span>
>

* ### Divide-and-Conquer
#### 將問題分割為<span class="blue">無關聯的子問題</span>，以Merge Sort為例
>若將一陣列[3,1,4,2]利用merge sort 進行排序，會先將陣列分割成[3,1]、[4,2]子陣列(即子問題)，其中<span class="red">[3,1]排序過程皆與[4,2]無關</span>，故我們知道子問題間彼此<span class="red">獨立</span>。
>
---

### **二、** 從Fibonacci理解Dynamic Programming
>已知Fibonacci關係式如下，請撰寫一程式計算F(n)
\begin{align}
&F(n)=\;\left\{
\begin{matrix}
F(0)=0\\
F(1)=1\\
F(n) = F(n-1) + F(n-2)\; \text{, n} \in \mathbb N \cap \text{n>1}\\
\end{matrix}
\right.\\
\end{align}

遇到Fibonacci想必各位腦中浮現的方法是遞迴呼叫，便能馬上寫出以下程式

#include <iostream>

using namespace std;

int Fibonacci(int n) {

    if (n <= 1) {
        return n; //F(0)=0 F(1)=1
    }
    
    return Fibonacci(n-1) + Fibonacci(n-2); //F(n)=F(n-1)+F(b-2)

}

int main() {
    int n;
    cin >> n;
    cout << "F(" << n << ") = "<< Fibonacci(n) << endl;
    return 0;
}

#### 但上面程式碼似乎有些問題，我們來觀察Fibonacci呼叫過程

:::warning
:warning: 時間複雜度$T(n)=$ $O(\varphi^n) ,\varphi \approx \text{1.6180}$，遞迴呼叫過程中，不斷重複計算Fibonacci次數遠大於實際需要計算的次數，隨著$n$增加，計算次數將指數成長
:::

### Dynamic Programming如何解決這個問題
仔細觀察遞迴呼叫過程中計算過的內容重複出現，是否能夠透過紀錄方式，將問題只<span class="blue">計算一次，</span>當要用到時能夠<span class="blue">重複使用</span>。Dynamic Programming正是基於以上想法，所衍伸出以下分支與方法

* ### Top Down Approach (Memoization)
### ==想法 (大問題->小問題)==
將原始問題分解成更小的子問題，如果子問題已經解決過了那麼直接回傳子問題解答，若沒有則持續分割為更小子問題並解決他。

:::success
此方法兼具遞迴的特性，並使用額外的空間紀錄遞迴解答，節省計算次數
:::

### ==程式碼==

#include <iostream>

using namespace std;

int Memoization[1000];

int Fibonacci(int n) {
    if (n <= 1) {
        return n; //F(0)=0 F(1)=1 Base Case
    }

    if (Memoization[n] != 0) {
        return Memoization[n]; //若已經計算過了直接回傳
    }
    
    return Memoization[n] = Fibonacci(n-1) + Fibonacci(n-2); //F(n)=F(n-1)+F(b-2)
   
}

int main() {
    int n;
    cin >> n;
    cout << "F(" << n << ") = "<< Fibonacci(n) << endl;
    return 0;
}

:::warning
:warning: 利用空間換取時間，透過大量的記憶體空間獲取更快的執行速度
:::
* ### Bottom Up Approach (Tabulation)
### ==想法 (小問題->大問題)==
既然已經知道大問題由許多小問題組成，那麼直接從小問題開始計算，最終可以組成大問題的解答

:::success
此方法利用迭代的特性，將解答不斷迭代，最終可獲得原始問題答案，其改善Memoization空間使用過度的問題
:::

### ==程式碼==

#include <iostream>

using namespace std;
int Fibonacci(int n) {  
  
  if(n <= 1) return n; //Base Case直接回傳
    
  int a = 0, b = 1, temp; //a代表temp前兩項，b代表temp前一項，temp代表目前Fibonacci
  temp = 0;
  for(int i = 2; i <= n; i++) {
    temp = a + b; //F(i) = F(i-1) + F(i-2) 透過迭代慢慢得出解答
    a = b;
    b = temp;
  }

  return temp;
}

int main() {
    int n;
    cin >> n;
    cout << "F(" << n << ") = "<< Fibonacci(n) << endl;
    return 0;
}

:::warning
:warning: 雖然解決Memoization空間問題，但並不代表Tabulation都是最佳解法，因子問題都需迭代一次，而Memoization只須查看真正用到的子問題
:::

### **三、** 總結
Dynamic Programming 將原始問題分解成各個<span class="blue">連貫性的子問題</span>看待，並思考子問題間的關聯性進行解題(以簡單推困難)，進而衍伸出兩大方法Memoization、Tabulation解決最佳化問題(Optimal Solution)，其中兩大方法比較如下

| | Tabulation | Memoization |
| ---- | ------------------------------ | -------------------------- |
|程式碼|較複雜|具備遞迴特性，內容簡單易讀|
|速度|快，直接迭代答案|慢，需要等待遞迴回傳|
|特性|迭代|遞迴|
|子問題解決情況|所有子問題都需計算一次|只需計算所需子問題|

## :link: 參考
---
* [Dynamic Programming (DP) Tutorial with Problems](https://www.geeksforgeeks.org/introduction-to-dynamic-programming-data-structures-and-algorithm-tutorials/)
* [MIT Introduction to Algorithms, Spring 2020](https://www.youtube.com/watch?v=r4-cftqTcdI&list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY&index=24)
* Introduction to algorithms 4th edition
###### tags: `Algorithm`