# Dynamic Programming 動態規劃
### Dynamic Programming 動態規劃

* 解決問題方式
> 透果組合子問題的解來解決原問題的方法
> 這些子問題彼此不獨立，會重複出現
> 每個子問題只解一次，把結果存進表格中之後遇到直接查表
* 用處
> 動態規劃通常用來優化問題
> 例如：找最大、最小值 (最短時間, 最少成本, 最多利潤, 最長序列, etc.)

#
### Four-step method 四步驟

1. **找出最佳解的結構**
* 一個最佳解怎麼由更小的最佳解組成的？
2. **寫出遞迴關係式**
* 大問題 = 小問題 + 成本
$$ dp[i] = min(dp[i-1] + cost,\ dp[i-2]+ cost) $$
3. **Bottom-up 計算**
* 不使用遞迴
* 從最小的問題開始填表
4. **重建解 (可選)**
#
### Assembly-Line Scheduling 生產線排程問題

> 工廠有兩條生產線，每條線有 $n$ 個站點我們用 $S_{i,j}$ 表示站點
> $i$ 代表哪條生產線 $j$ 代表第幾個站 $a_{i,j}$ 表示該站點的時間 $t_{i,j}$ 表示前一站轉換過來的時間
> 每條生產線都有進入時間 $Entry \ Times$ 以$e_1$ , $e_2$表示
> 離開時間 $Exit \ Times$ 以 $x_1$ , $x_2$ 表示
> 每經過一個站都有兩種選擇，留在同原先產線or轉去另一條產線，保留無成本 轉換有時間成本

#### 找最短時間方法：

* Brute force 暴力窮舉
你有 $n$ 個站點就有 $2^n$ 種可能性，在 $n$ 很大時不可行

* Four-step method

* 時間複雜度：$Θ(n)$

**1. 找出最佳解結構：**
* 先分析第一條產線 $S_1$
* $j = 1$ 時只有可能是 $S_{1,1}$
* $j = 2$ 時有兩種可能，留在 $S_{1,j}$ 過來或 $S_{2,j}$ 轉換過來的
* 所以走到 $S_{1,j}$ 最快方式只可能來自 $S_{1,j-1}$ 走來或是 $S_{2,j-1}$ 轉過來
* $S_2$ 同樣道理省略

**2. 寫出遞迴關係式：**
* 先定義好 $f_i[\ j\ ] = Fastest \ time \ through \ S_{i,j}$
* 遞迴關係式可以寫成這樣\begin{cases}
f_i[\ 1\ ]=e_i+a_{i,1}\\f_i[\ j\ ]=min(f_i[\ j-1\ ]+a_{i,j} \ \ ,\ f_{3-i}[\ j-1\ ]+t_{3-i,j-1}+a_{i,j}) \ \ \ ,for \ j\ge2\end{cases}
* 那麼最快時間就能定義成 $f^*=min(f_1[\ n\ ]+x_1\ ,\ f_2[\ n\ ]+x_2)$

**3. Bottom-up計算：**
* 從最小的數字帶入計算後填表
#### Example：

* $f_1[j]$ 遞迴關係式如下：
\begin{cases}
f_1[\ 1\ ]=e_1+a_{i,1}\\f_1[\ j\ ]=min(f_1[\ j-1\ ]+a_{1,j} \ \ ,\ f_2[\ j-1\ ]+t_{2,j-1}+a_{1,j}) \ \ \ ,for \ j\ge2\end{cases}
* 最假解為 $f^*=min(f_1[\ n\ ]+x_1\ ,\ f_2[\ n\ ]+x_2)$
* 從最小的數字帶入計算後填入表格中，$f_2[j]$ 同理帶入
| $j$ | $\ 1$ | $\ 2$ | $\ 3$ | $\ 4$ | $\ 5$ |$\ 6$|
| :--------: | :--- | --- | --- | --- | --- |---|
| $f_1[j]$ | $\ 9$ | $18$ | $20$ | $24$ | $32$ |$35$|
| $f_2[j]$ | $12$ | $16$ | $22$ | $25$ | $30$ |$37$|

* $f^*=min(35+3,37+2)=38$

#### 偽代碼參考

#### **為什麼要用Bottom-up?**

* Top-down fashion： $Θ(2^n)$
遞迴重複計算 -> `指數時間`
* Bottom-up fashion：$Θ(n)$
表格記錄狀態 -> `線性時間`

#
### Matrix Multiplication 矩陣相乘

> 矩陣 $A:p*q$ , $B:q*r$ 相乘結果 => $C:p*r$
> 所花的時間會是 $O(pqr)$
#### 矩陣乘法的偽代碼：

#### fully parenthesized 完全加括號：

> 用括號來表示計算順序，只需要看括號就能知順序了

$<A_1,A_2,A_3,A_4>$

我們可以寫成以下幾種形式：
* $(A_1(A_2(A_3A_4)))$
* $(A_1((A_2A_3)A_4))$
* $((A_1(A_2A_3))A_4)$
* $(((A_1A_2)A_3)A_4)$
* $((A_1A_2)(A_3A_4))$
> 這五種形式代表著五種矩陣乘法計算順序
> 乘績會相同但是乘法次數會不同
> 在此我們動態規劃找出的就是矩陣乘法次數最少的那個

#### Example：
$<A_{1(10\times100)},A_{2(100\times5)},A_{3(5\times50)}>$
* $((A_1A_2)A_3):10\times100\times5+10\times5\times50=7500$ 次乘法
* $(A_1(A_2A_3)):100\times5\times50+10\times100\times50=75000$ 次乘法

#### 矩陣乘法的動態規劃問題：
給你一串矩陣 $<A_1,A_2,...,A_n>\;of\ n\ matrices$
fully parenthesize the product $A_1A_2...A_n$
請你找出最少乘法次數的組合

* Brute force 暴力窮舉
* 時間複雜度 $Ω(2^n)$

* Four-step method

* 時間複雜度：$Θ(n^3)$ , 空間複雜度：$Θ(n^2)$
1. 找出最佳解結構：
* 先觀察一下
另 $A_{i..j}=A_iA_{i+1}...A_j\ ,i<j$
我們找一個 `index` $k$ 當作最佳的斷點
則 $A_{i..j}=A_{i..k}A_{k+1..j}\ ,i\le k\le j$
* `cost` 就會是 $A_{i..k}+A_{k+1..j}+A_{i..k}A_{k+1..j}$ 次乘法
2. 遞迴關係式：

* $m[i][j]=\begin{cases}\;0\qquad,if\quad i=j \\
\;min_{i\le k < j}\ \{\;m[i][k]+m[k+1][j]+
P_{i-1}\times P_k\times P_j\ \}\quad ,if\quad i<j\end{cases}$
* 再定義一個 $s[i][j]=k$ 當 $m[i][j]$ 的最佳解是從某個 $k$ 切開時就記錄下來
3. Bottom-up：
*  $P_{0\sim6}$組成$A_{1\sim6}$個矩陣

* 
帶入遞迴關係式中填表， $i=j$ 時直接填入 $0$

* 
接著算下去3個矩陣相乘後填表

* 

4個矩陣相乘填表
* 

5個矩陣相乘填表

* 

6個矩陣相乘填表

* 

S表

#
### Subsequence 子序列
> 子序列說白話就是原本的序列隨機抽取一些元素出來，但順序不能改變
> 舉例來說 $Z=\langle 1,2,4,3,9,6,7\rangle$
> 那 $X=\langle 1,2,4,9,7\rangle$ 就是 $Z$ 的子序列
> $Y=\langle 2,4,7\rangle$ 就是 $Z,X$ 兩者的共同子序列
#
### Longest Common Subsequence Problem 最大共同子序列問題

> Given two sequences $X=\langle x_1,x_2,...,x_m\rangle$ and $Y=\langle y_1,y_2,...,y_n\rangle$
> find a maximum-length common subsequence of $X$ and $Y$

* Prefix of sequence
* $i^{th}$ prefix of $X$ is $X_i=\langle\; \underbrace{ x_1,...,x_i}_{i=0,1,..,.m}\;\rangle$
* **Example：**
$X=\langle\; A,B,C,B,D,A,B\; \rangle$
* $X_4=\langle\; A,B,C,B\; \rangle$
* $X_0=\langle \; \rangle$
* $X_6=\langle\; A,B,C,B,D,A\; \rangle$

* **最佳解的結構：**
* 令 $X=\langle\; x_1,...,x_m\; \rangle$ , $Y=\langle \; y_1,...,y_n\; \rangle$
* $Z=\langle \; z_1,...,z_l\; \rangle$ 是 $X\ \&\ Y$ 的某一個 `LCS`
* 會有三種情況
1. $x_m=y_n$ then $z_k=x_m=y_n$ and $Z_{k-1}$ is an `LCS` of $X_{m-1} \ ,Y_{n-1}$
2. $x_m\not=y_n$ then $z_k\not=x_m\Rightarrow Z$ is an `LCS` of $X_{m-1}\ ,\ Y$
3. $x_m\not=y_n$ then $z_k\not=y_n\Rightarrow Z$ is an `LCS` of $X\ ,\ Y_{n-1}$

* **遞迴關係式：**
* Overlapping
* find $LCS(X,Y)$ need to find $LCS(X,Y_{n-1})$ and $LCS(X_{m-1},Y)$ first
* $LCS(X,Y_{n-1})$ and $LCS(X_{m-1},Y)$ both need $LCS(X_{m-1},Y_{n-1})$ first
* 計算重複問題 -> 定義DP狀態存起來用動態規劃

* Define $c[i][j]=length\; of\; LCS(X_i,Y_j)$
* $c[i][j]= \begin{cases}\; 0\qquad &\text{if}\;i=0\text{ or } j=0\ ,\\
\; c[i-1][j-1]+1\qquad &\text{if }i,j>0 \text{ and }x_i=y_j\ ,\\
\; max(\ c[i-1][j]\ ,\ c[i][j-1]\ )&\text{if }i,j>0 \text{ and }x_i\not= y_j\ .
\end{cases}$

* **Bottom-up 計算：**
* 以投影片中的例子來說，$X=\langle A,B,C,B,D,A,B\rangle$ , $Y=\langle B,D,C,A,B,A\rangle$
*  填表
* 
箭頭+填表
* 時間複雜度： $O(mn)$