Dynamic Programming (DP)(動態規劃)

使用recurrsion來計算，固然方便，但缺點就是計算費時，因為recurrsion不會記憶之前算過的答案，一樣的輸入值會重新計算，造成cpu忙碌，需計算龐大數值，不適合使用。
這時動態規劃(Dynamic Programming)就可以解決recurrsion效率低下的問題， 利用空間換取時間，把問題切成最小的子問題創建表格，供紀錄計算結果，再比對出最佳的解答填到表格，另一小問題得出最佳解答填到表格，再最佳解和最佳解合併成大一點問題再找最佳解答填到表格，直到合併到問題本身，由表格就可查到所要的資訊。

相對位置 & DP最佳解 說明

假設在聲控系統上的一個資料為一組波形為"{'請','開', '門'}"，現在有五個人要開門，只要能說最接近答案，就能開門，一樣相似的話都可以開，
第一個人說"{'門','請','開'}"
第二個人說"{'請','~','~','開','啊'}"
第三個人說"{,'開','~', '門', '吧'}"
第四個人說"{'請','不','開','~', '門', '吧'}"
第五個人說"{'門','開','~', '~', '吧'}"

判斷結果:
第一個人字都對，但一個字順序不一樣(雖然中文語意沒有差別)，系統只認照順序的的字詞，沒有定義"門請開"是什麼意思，最長關聯就是"請開"，所以算出來LCS為2。
第二個人加了語氣和狀聲詞但也不影響整句話的意思，最長關聯就是"請開"，計算LCS為2。
第三個人也加跟第二個人一樣有語氣和狀聲詞，最長關聯就是"開門"，算出來LCS為2。
第四個人是重點，最長關聯就是"請開門"，計算出來LCS為3。
第五個人，最長關聯就是"門"或"開"，計算出來LCS為1。

所以系統會讓第四人通過門。
但是語意上"請不開門"卻讓他開門是不對的，所以我們要確保使用DP時，要確定最佳解的定義不能有什麼。

What if?
今天沒有第四個人，那系統會讓第一個人、第二個人和第三人通過。

LCS (Longest common subsquence)

Definition
簡易說明:
找出兩者資料之間，內容的相對位置有相同的地方，且這關聯的長度為最長的結果。

最長共同子序列的長度可能有長度相同，序列內容不同的情況。
有兩序列abcbc和aaccb，它們最長共同子序列長度為3，但可能為acc或者acb。

Minimum Edit distance

Definition
簡易說明:
找出最短不同的地方的的總長度或修改最少的方式的次數。
重點就是: 新增(insertion), 刪除(deletion), and 修改(modify)
這三類的加權，可由應用方式不同加以修改。

Reduce difficulty

\( \text{LIS (Longest Increasing Subsquence)} \rightarrow \text{LCS (Longest Common Subsquence)} \rightarrow \text{Edit Distance} \)

轉換過程:

  1. 有個序列S，需求LIS(最長遞增的元素)，將這個問題轉換成LCS問題，作法為:
    LCS是將兩序列做最長相對位置的相同元素，所以假設\( A=S \)， \( B=S^* \)(這裡\( S^* \)為將S裡元素從小排到大的序列)\( \rightarrow \text{LIS}(S) = \text{LCS}(A,B)\)。
  2. 將LCS問題轉換成Edit Distance問題:
    一樣上面A,B兩序列不變，這裡給X=A, Y=B，懲罰加權為Insertion=1, Deletion=1, Substitution=\( \infty \)，這樣兩序列一定不會去做Substitution。 \[ |\text{ED}(X,Y)| = |A|+|B|+2\cdot |\text{LCS}(A,B)| \]
  3. 設\( f: \text{LIS}(S)\rightarrow \text{LCS}(A,B) \)， \( g: |\text{ED}(X,Y)| = |A|+|B|+2\cdot |\text{LCS}(A,B)| \)，則\( h: \text{LIS}\rightarrow \text{ED} \)，\( h=f\circ g=f(g) \)為唯一函數，所以LIS問題是可以降為Edit Distance問題的。

LCS和Edit distance應用

收集來的資料，像是圖片、影像、聲音或DNA序列，會把這些資料轉換成一串數字儲存起來。
比對資料時，在機器看來，只要加一點人類無法輕易辨識的雜訊、少了一點特徵、一個像素或一個數字不一樣，整個資料就當成是新的。
所以最長共同子字串和最短Edit distance的演算法就成為了生物資訊極為重要的學問，經由比對得出最相關的資料，也就是相似越多或不相關的越少，即為可能所求答案。
經由回推，也可以得出差異，用來更新檔案等應用。

使用DP解決的問題

Make Change (換零錢問題)

目的是換到到最少個數/張數的錢。
Example

Knapsack problem(背包問題)

不考慮背包空間，但考慮負重問題，物品之間的重量不相等，其價值為單位重量的價值來區分，有分兩種討論，一是物品是可分割的，二是物品是不可分割來討論。
More discussion

Matrix-Chain Multiplication Problem

計算矩陣乘法和加法的個數
假設有三個矩陣A,B,C要乘法，\( A:10\times 100 \), \( B:100\times 5 \), \( C: 5\times 50 \)，乘法的的結果要是\( ABC \)。
有兩種算法可以得到答案
一為\( A(BC) \)，二為\( (AB)C \)。
如果用\( A(BC) \)計算，需要算\( (10\times 100\times 50)+(100\times 5\times 50)=75000 \)個乘法。
則使用\( (AB)C \)計算，需要算\( (10\times 100\times 5)+(10\times 5\times 50)=7500 \)個乘法。
差異到十倍，所以計算出最小的乘法方式，是提升計算效能重要指標。
但要找出最小的乘法量的方法有\( (n-1)! \)種中找尋，因matrix-chain multiplication有最佳結構解，所以使用動態規劃可以有效的找到最小乘法量的答案。
more...

Optimal Binary Search Tree (OBST)

當搜尋的每個點有權重時，平衡對稱的binary tree不一定有最小的平均搜尋次數。
最小平均搜尋樹