Dynamic Programming (LCS)
之前有寫過類似的問題，但是這次討論的比較偏向理論一點。
有興趣的朋友，請留步收看～～
Outline:
- Dynamic Programming主要的四個步驟
- 例題示範：Longest-Common-Subsequence Problem（最長共同子序列）
- Dynamic Programming的特性（補充）
- 結論
在上一篇提到，動態規劃的精神就是「畫表格」，用比較學術一點的講法是tabular method。
另外，動態規劃的技巧，常常用在尋找「最佳化問題」。也就是說，問題可能如：怎麼樣可以找到最佳的值？什麼情況下可以獲利最多？等等。
Ex: Shortest path, LCS…
＊注意：上面所提到的「常常」，代表的是usually，並非總是(alaways)。
Dynamic Programming 主要的四個步驟
- 理解大問題與小問題之間的關係（特徵）找出來
- 找到關係（特徵）後，寫出遞迴關係式
- 從小問題最佳解，解出來後，填入表格，一步一步慢慢往上，再解出大問題，大問題則可以透過查詢表格得到答案。
- 已經有大表格之後，可以透過原本的表格，去找出來，這個最佳（最小）問題是怎麼得到的。
在一開始學可能會覺得只要可以解題就可以了，為什麼還需要這些步驟？
事實上，每一個問題，都可以使用不同的演算法去解。
當有一個新的問題，我們想要找出最好的演算法，但不知道應該要用什麼樣的方法去實作他，這時可能就會先把基本的幾個演算法拿來嘗試看看。而嘗試的方法需要先把問題拆解，再去找到符合某演算法的特色。
假設這次嘗試用 Dynamic Programming的方式去寫出這個程式的話，就可以透過這四個步驟，將問題拆解，方便找到屬於DP的演算法。
例題示範：Longest-Common-Subsequence Problem（最長共同子序列）
問題敘述，題目給出兩個字串(x=<x1, x2, x3, …>, y = <y1, y2, y3, …>)，想問裡面共同的序列為何?
那就照我們剛剛所說的步驟開始吧～
STEP 1：理解此問題，並找出問題之間的關係
這邊可能有人會好奇說，為什麼從最後一個字元，往回推？
因為 DP的特色是先解小問題，再從小問題解出大問題，所以為了STEP2的遞迴關係，先分析大問題是怎麼得到的，以方便構建出遞迴關係。
STEP 2：找出「遞迴關係式」
因為我們要問的是「最長共同子序列」，相對的也想知道有幾個「相同的字元」，也就是相同字元的個數有多少。
假設len[i, j]，代表Xi, Yj間目前共有幾個相同字元。
STEP3：畫出表格
依照Step2的公式畫出此表格。
表格放大圖
STEP4：求出最佳解（最佳解從何而來？）
此問題重視的是，這個解是怎麼得到的。例如：今天搭火車去高雄，查了時刻表，找到一個時間最短的路線，就會好奇說，是因為停靠了哪幾站，所以花得時間最少。
有了上述概念後，再重新再看一下上面那張圖，最後得到的4，是因為哪幾個「相同的字元」，才使這個表格中，Ｘ和Ｙ「最常共同子序列」的長度為 4呢？
表格放大圖：
找到共同字串：
從上面的範例，再來延伸出Dynamic Programming的更多性質。
Dynamic Programming的特性（補充）
- Optimal Substructure
大問題的答案，不用重新開始找，只是要從子問題的答案中將大問題的答案給「拼湊」出來。
注意：
任何的 optimal problem都會有 optimal subproblem ?
Ans:並不是所有的問題都有此特性。
Optimal Substructure，通常會分成兩部分來討論：
- 有多少個子問題(subproblem)
- 有多少選擇(choice)來決定子問題(subproblem)
範例：
— 以上面所提的 LCS problem為例
1 subproblem(X和 Y的字元是否相同)
可能情況(choice)（兩種）：x, y 相同, x y 不相同
- Overlapping subproblems
子問題常常在重複，解相同的問題。
例如：之前提過的「費氏數列」，fib(1)會一直重複被計算到，如果可以畫表格去紀錄的話，在大問題中，遇到相同表格，就可以直接拿來使用。在這邊成為「動態規劃」的一項特性overlapping subproblem。
另外從圖中，得知，動態規劃是先處理小問題，再用小問題的答案，去解決大問題。(Bottom-up)
注意：
Divide & Conquer屬於Top-down，從大問題拆開成小問題，在從小問題組合回大問題。（用 Merge Sort的圖應該就可以理解他們之間的差異。）
結論：
- Dynamic Programming 通常用來解決最佳化問題
- 兩個重要性質：Optimal substructure, overlapping subproblems
- 「建立表格」的精神
- Bottom-up
主要是從老師上課內容，再自行做成筆記，如有錯誤還請各位多多指教～～
希望這篇也能幫助到對LCS困惑的朋友，那我們就下次再見吧。
