Dynamic Programming(DP) — 動態規劃(下)
Dynamic Programmin的經典應用除了斐波那契數之外，還有背包問題、最短路徑問題、河內塔、LCS等等，那麼我們就試著用Dynamic Programming來解 leetcode的1143題 longest common subsequence (LCS)吧!
甚麼是common subsequence?
由於common subsequence和common substring常常被搞混，因此先來理解這兩者的差異吧!
- common subsequence — 文字的集合出現的順序是一樣，不一定有連續性 ex abcd, abd
- common substring — 連續的文字出現在兩個字串裡 ex ab, abc
因此LCS就是尋找出字串當中最長的common subsequence
假設現在有兩個字串ANB和AKB，要求得LCS的長度的流程會如下
- 從字串的最後一個字開始檢查
- 如果相同則次數+1，將相同的文字去掉後繼續比較
3. 當最後一個字不相同時，則會有兩種可能性
- A字串的最後一個字可能與B字串的倒數第二個字相同
- B字串的最後一個字可能與A字串的倒數第二個字相同
因此拆解成兩個子問題"A"與"AK"比較 以及"AN"與"A"比較
4.持續的分解問題…
先試著用遞迴解題
不過這題如果用遞迴解的話，leetcode執行效率會非常的差，會顯示Time Limit Exceeded，如下圖
使用Dynamic Programming
在用Dynamic Programming 解LCS的時候，通常會用矩陣圖來記錄比較的結果，如下圖，將比較的兩個字串各自作為x軸和y軸，兩兩比較找出相同的字母，並且搭配箭頭與數字來做標記
矩陣圖的規則如下
- 空字串與任何單字比必定不相同，因此填入0
- 若兩者的值不同，則比較上方和左方的格字數字大小
- 上方比較大標記為↑
- 左方比較大則標示為 ←
- 上方與左方的數字大小相同則統一標記為↑
3. 若兩者的值相同，則取左上方的值+1，並且標記為↖
依序填完數字就會發現，對角線的右下方數字即為LCS的長度，從最大的數字開始，沿著箭頭的方向走，走過的格子用黃色圈圈標記，將紅色箭頭的所代表的字母收集起來就會得到LCS的字串，在js中習慣以二維陣列來模擬矩陣圖，因此將上方的圖片轉化為二維陣列就會如下圖
接下來試試看畫出 "ABCBDABC" 和 "BDCABAC"這兩個字串的LCS矩陣圖吧!
依照箭頭方向收集紅色的箭頭就可以取得LCS為"BDABC"
用js的二維陣列來表示的話會如下圖
用js實作Dynamic Programming
最後成功用Dynamic Programming解出 longest common subsequence !，雖然執行時間和占用記憶體不盡理想…還有待優化
