Uva 526 - String Distance and Transform Process

Problem#

字串距離是一個代表兩個字串的非負整數。接著要轉換(transform)$a$字串至$b$字串，有三種操作：插入(Insert)、刪除(Delete)、及取代（Replace)。
字串距離就是轉換的數量，求任意$a$字串轉換至$b$字串的字串距離及如何轉換的。

每筆case有兩行字串$a$、$b$，以EOF結尾，字串的長度不超過$80$

每筆輸出第一行為一個整數($n$)，代表字串距離(String distance)。
接著有有$n$行，每行為一個操作指令，格式如下：

abcac
bcd
aaa
aabaaaa

3
1 Delete 1
2 Replace 3,d
3 Delete 4

4
1 Insert 1,a
2 Insert 2,a
3 Insert 3,b
4 Insert 7,a

dp[i][j]代表從a[1..i]到b[1..i]的最小字串距離。
a[i], b[i]都是1-index

紅色箭頭：當a[i] != b[j]時
- 從上方、左方、左上方挑一個最小的，然後字串距離+1
  - 往下:刪除a[i]字元
  - 往右：插入b[j]字元
  - 往由下：把a[i]字元取代成b[j]字元
藍色箭頭：當a[i] == b[j]時
- 不用做變換，所以字串距離一樣。
範例

  j 0 1 2 3
i +--------
0 | 0 1 2 3
1 | 1 1 2 3
2 | 2 1 2 3
3 | 3 2 1 2
4 | 4 3 2 2
5 | 5 4 3 3

* `dp[5][3]` 及為$a$到$b$的最小字串距離