題目連結：
題目大意：
輸入有多筆測試資料，每筆佔兩列。兩列各自給定一正整數以及一字串，代表有一字串之長度 |S| 以及字串 S 之內容、還有另一字串長度 |T| 和該字串 T 之內容。
現在有三種操作：
刪除 S 的其中一個位置的字元、
在 S 的某個位置中插入一個字元、
把 S 某個位置的字元變成另一字元。
試問最少要多少操作可以使得 S 變為 T ？
範例輸入：
10 AGTCTGACGC
11 AGTAAGTAGGC
範例輸出：
4
解題思維：
稍微簡化的最小編輯距離（Minimum Edit Distance）之題型。
最小編輯距離與最長共同子序列（Longest Common Subsequence，LCS）有異曲同工之妙。作法跟遞迴式都十分相似，但是最不一樣的是初始條件。
因為本題只求最小的操作數，因此將刪除、新增以及變換的「成本」都視為 1 。因此將成本值代入典型的最小編輯距離求出的最小成本即是本題的所求。
定義 Ei,j 為字串 S[1:i] 變為 T[1:j]（A[i,j] 代表第 i 個（含） ～ 第 j 個（含）字元（此處的字串索引值從 1 開始）形成之子字串，當 i > j 定為空字串），其所需最少操作數。可看到遞迴式：
當 S[i] = T[j] 時，Ei,j = Ei-1,j-1；
當 S[i] ≠ T[j] 時，Ei,j = min(Ei-1,j-1 + C, Ei,j-1 + I, Ei-1,j + D)。
其中 C 、 I 、 D 依序代表變換、新增以及刪除字元的成本，在本題皆等於 1 。且初始條件為：
E0,0 = 0；
Ei,0 = i × D 對於 i ≧ 1 。因為此時 T 為空，則依序刪除 S 的所有字元即可；
E0,j = j × I 對於 j ≧ 1 。因為此時 S 為空，則依序新增 T 的所有字元即可。
接著就從 i = 1 到 |S| ，對於每個 i 值從 j = 1 到 |T| 之雙重迴圈去依序求出每個 Ei,j 。最後，E|S||T| 即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
