主題
題目連結：
題目大意：
輸入有多筆測試資料，每筆佔四列。測資第一列給定一字串，代表目標字串。接著的三列輸入，每列給定一字串，代表其中一隻猴子打出來的文字（第一列代表編號 1 的猴子、第二列為編號 2 、第三列編號 3）。
跟昨天的題目類似，現在有刪除、新增以及變換字元三個操作。但是這三個操作現在有了各自的成本值，依序是 2 、 2 以及 3 。
試問，哪隻猴子打出來的文字與目標字串的最小編輯距離（Minimum Edit Distance）之成本最小，而該最小成本值又是多少？如果有多隻猴子的編輯成本一樣則，挑編號較大的。
注：所有字串皆不超過 L = 10 ^ 4 個字元且至少有一字元長。
範例輸入：
範例輸入 #1
abc
bcd
cde
efg
範例輸入 #2
abcd
abcde
abc
bcd
範例輸出：
範例輸出 #1
1 4
範例輸出 #2
3 2
解題思維：
參見題目大意區域給定的鏈結（即昨天的解題心得），昨天與今天都是最小編輯距離（Minimum Edit Distance）之題型。
但是本題的刪除、新增、變換是有成本的，將這些成本值代入昨天的作法求出每隻猴子之文字與目標字串的最小編輯成本之後，看誰最小即是所求。
不過，因為本題的字串長度可以到不小，因此如果像昨天那題一樣開一個 (L + 1) × (L + 1) 大小的陣列會超出記憶體許可。而我們可以看到每次求一項 Ei,j ，其只會用到該列（i）以及前一列（i - 1）的位置（根據遞迴式確實如此），所以我們可以只用兩個長度為 (L + 1) 的陣列然後交互使用即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
